Home›Mobile agents on graphs›Exploration›Graph exploration by a single agent

Graph exploration by a single agent

One agent starts at a node of an unknown anonymous graph and must visit every node; how much memory does it need, which pebbles or knowledge make it possible, and how fast can it be?

Problem statement and measurescollapse

Exploration of a tree by the rule Choose-Next of Diks et al. 2004: the agent leaves the start node \(s\) by port 1 and, entering a node of degree \(d\) by port \(i\), leaves by port \((i \bmod d) + 1\). It walks around the tree, each edge once in each direction, and is back at \(s\) after \(2(n-1)\) moves with every node visited (perpetual exploration repeats this tour). One frame per move.

A single deterministic agent is placed at a node \(s\) of a connected graph \(G\) with \(n\) nodes, \(m\) edges and maximum degree \(\Delta\). Nodes are anonymous (they carry no names the agent can read), and the edges at each node are numbered locally; these numbers are the node's ports. The agent sees the degree of its node and the port by which it entered. It must visit every node of \(G\). Three termination requirements are standard:

perpetual exploration: every node is eventually visited; the agent never has to stop;
exploration with stop: every node is visited and the agent then stops, anywhere;
exploration with return: every node is visited and the agent stops at \(s\).

Return implies stop, and stop implies perpetual exploration. Memory is the number of bits of the agent's state; when the agent carries pebbles (objects it can drop on a node and pick up again) their number is reported with the memory. Time is the number of moves (edge traversals) until exploration is complete; for periodic exploration it is the period. Unless a variant says otherwise the agent knows nothing about \(G\), not even \(n\).

Exploration is the oldest problem of the mobile-agent literature: it started as maze search by finite automata, and the question of how little memory suffices runs from Budach's impossibility (1978) to Reingold's log-space algorithm (2005). Several agents exploring together form the sibling problem, collaborative exploration.

Measures: Time, edge traversals until every node is visited (for periodic exploration: the period); Memory, bits of agent memory; pebbles, if any, are counted separately.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine a small cleaning machine put down in a large building with no map, where every room looks the same. We model the building as a graph: rooms are nodes and corridors are edges (each edge joins two nodes), and the machine is an agent that walks from node to node along edges; one crossing of one edge is a move. \(n\) is the number of nodes and \(m\) the number of edges; the degree of a node is the number of edges at it, and \(\Delta\) is the largest degree. At each node the edges are numbered \(0, 1, \dots\); these numbers are called ports, and the numbering at one node has nothing to do with the numbering at the next. The agent sees only the degree of its current node and the port by which it came in; nodes are anonymous (they have no names), so it cannot tell a node it has seen before from a new one. In the basic version (perpetual exploration) it must eventually visit every node of every connected graph, without ever having to stop, and the question is how few bits of memory (what the agent keeps from one move to the next) make this possible.

1AlgorithmLeave by the next port (trees) Trees, perpetual exploration → Diks et al. 2004

This is the algorithm Choose-Next of Diks et al. 2004, for graphs without cycles (trees); here the ports of a node of degree \(d\) are numbered \(1, \dots, d\).

Leave the start node (the node where you are placed) by port 1.
When you enter a node of degree \(d\) by port \(i\), leave it by port \((i \bmod d) + 1\), the next port in cyclic order (at a node of degree 1 this sends you straight back).
Repeat forever.

Why it works and what it costs. On a tree this is the rule "keep your right hand on the wall": the agent walks around the tree, and every edge is walked once in each direction before the walk repeats, so all \(n\) nodes are visited within \(2(n-1)\) moves. The agent only has to remember one port number, which Diks et al. 2004 count as \(O(\log\Delta)\) bits, and they show that \(\Omega(\log\Delta)\) bits are needed on trees, so this is optimal. On graphs with cycles the same rule can go round a cycle forever and miss nodes; there the right amount of memory is \(\Theta(D\log\Delta)\) bits, with \(D\) the diameter (the largest distance between two nodes) Fraigniaud et al. 2005a.

Why it matters. Choosing the next port from the entry port alone is the basic move of almost every memory-efficient exploration algorithm, and the universal exploration sequences used for general graphs are a generalisation of it.

2ImpossibilityNo stopping on a ring without a pebble Exploration with stop, nothing known → Dieudonné & Pelc 2012

Ask for more: the agent must visit every node and then stop, without knowing \(n\) and without a pebble (an object it could drop on a node to recognise that node later). Take rings (cycles) of every size, numbered so that at every node port 0 leads clockwise and port 1 counterclockwise. In such a ring every node has degree 2 and every arrival looks the same, so what the agent sees never depends on the size of the ring. A deterministic agent (one with no random choices) therefore makes the same sequence of moves in every such ring. Since it explores and stops in, say, the ring of 3 nodes, it stops after some fixed number \(T\) of moves, and it does the same in the ring of \(T+2\) nodes.

Why it holds. In \(T\) moves the agent can visit at most \(T+1\) different nodes, so in the ring of \(T+2\) nodes at least one node is never visited: the agent stopped too early. Extra memory does not help, because the problem is not remembering but recognising: the agent can never tell "I am back where I started" from "this is a new node that looks the same". This is why every stopping variant in the catalogue adds a pebble or knowledge of a bound \(N \ge n\) Dieudonné & Pelc 2012.

Why it matters. It shows that the hard part of exploration is often knowing when you are done, a theme that returns in dispersion, rendezvous and gathering.

3AlgorithmRandom walk Randomized exploration when \(n\) is known → Aleliunas et al. 1979

Allow the agent to flip coins, and tell it a number \(N \ge n\).

At each node, pick one of the ports uniformly at random and take its edge.
Count the moves; stop after \(2N^3\) moves.

Why it works and what it costs. Aleliunas et al. 1979 proved that a random walk visits every node of a connected graph within \(2m(n-1)\) moves on average. Since \(m \le N^2/2\) and \(n - 1 < N\), this average is below \(N^3\); a walk that runs twice as long as its average cover time fails to cover the graph with probability at most \(1/2\) (Markov's inequality), and repeating the walk lowers the failure probability further. The agent needs only a counter, \(O(\log N)\) bits. A deterministic agent with the same memory also exists, but its algorithm (Reingold's log-space construction) is much harder Reingold 2008.

Why it matters. The random-walk bound was the starting point for universal traversal and exploration sequences, which turn the random walk into a fixed list of port choices that works on every graph.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Memory

Arbitrary graphs, perpetual exploration standard

The classical memory question: how many bits must a finite-state agent have to visit every node of every graph of diameter \(D\) and degree \(\Delta\)?

unknown — vs —

tight \(O(D\log\Delta)\) vs \(\Omega(D\log\Delta)\) trap graphs

Trees, perpetual exploration

On trees, perpetual exploration needs exactly \(\Theta(\log\Delta)\) bits: enough to remember a port.

unknown — vs —

tight \(O(\log\Delta)\) vs \(\lceil\log\Delta\rceil\) port addressing

Exploration with stop, nothing known

Without a bound on \(n\) and without a way to mark a node, an agent can never be sure it has seen everything.

impossible — vs \(\text{impossible}\) no way to recognise the start

Trees, exploration with stop

Stopping on a tree without knowing \(n\) needs more than constant memory, but how much more is open: \(\Omega(\log\log\log n)\) against \(O(\log n)\).

unknown — vs —

polynomial gap \(O(\log n)\) vs \(\Omega(\log\log\log n)\) deciding when to stop

Exploration with return and pebbles

\(\Theta(\log\log n)\) pebbles are necessary and sufficient for a constant-memory agent, which then explores in polynomial time and returns to the start without knowing \(n\).

unknown \(n^{O(1)}\) vs —

tight \(O(1)\ \text{bits},\ O(\log\log n)\ \text{pebbles}\) vs \(\Omega(\log\log n)\ \text{pebbles}\) trap graphs

Memoryless automaton with pebbles

A deterministic memoryless automaton (one state) explores every connected graph with 2 pebbles, and 2 is the minimum.

unknown — vs —

tight \(0\ \text{bits},\ 2\ \text{pebbles}\) vs \(2\ \text{pebbles}\) trap graphs

Exploration with stop when \(n\) is known

Reingold's log-space universal exploration sequences give an \(O(\log n)\)-bit agent that explores and stops in polynomial time.

unknown \(n^{O(1)}\) vs —

near-optimal \(O(\log n)\) vs \(\omega((\log n)^{1-\varepsilon})\) trap graphs

Randomized exploration when \(n\) is known

A random walk covers any graph in expected \(2m(n-1)\) steps; with a step counter and a bound on \(n\) it stops after exploring with good probability.

unknown \(O(mn)\) vs —

unknown \(O(\log n)\) vs —

Exploration with stop and one pebble

One pebble makes stopping possible; the agent then needs \(\Omega(\log n)\) bits.

unknown — vs —

polynomial gap \(O(D\log\Delta)\) vs \(\Omega(\log n)\) reduced automata

Trees, exploration with return

Returning to the start on a tree takes \(\Theta(\log n)\) bits.

unknown — vs —

tight \(O(\log n)\) vs \(\Omega(\log n)\) pigeonhole on start nodes

Node labels chosen by the designer

With three-valued labels on the nodes, an agent with fewer than 25 states explores every graph and stops after at most \(20m\) edge traversals.

unknown \(O(m)\) vs —

tight \(O(1)\) vs —

Port numbers chosen by the designer (periodic exploration)

If the designer may set the port numbers, a constant-memory agent visits every node periodically with period between \(2n-2\) and \(3.5n-2\).

tight \(3.5n-2\) vs \(2n-2\) every tree edge twice

tight \(O(1)\) vs —

Directed graphs, one pebble

An agent that cannot walk back along an arc needs \(\Omega(n\log\Delta_{out})\) bits, even with up to \(n\) pebbles; with one pebble, \(O(n\Delta_{out}\log n)\) bits suffice, in exponential time.

unknown \(\text{exponential}\) vs —

polynomial gap \(O(n\Delta_{out}\log n)\) vs \(\Omega(n\log\Delta_{out})\) no backtracking

Directed graphs, one pebble, bound on \(n\) known

With a bound \(N \ge n\), one pebble lets an agent map any strongly connected digraph in polynomial time.

unknown \(O(N^2 n^6 \Delta_{out}^2)\) vs —

unknown — vs —

Directed graphs with labelled nodes

An agent that recognises nodes but cannot backtrack must traverse every arc; the cost depends on the deficiency \(\phi\) of the digraph.

polynomial gap \(O(\phi^8 m)\) vs \(\Omega(\phi^2 m)\) unbalanced arcs

unknown — vs —

Dynamic rings

On a \(T\)-interval-connected ring whose edges may be missing for up to \(\delta\) steps, the worst-case exploration time is known exactly up to additive terms.

tight \(n+\tfrac{n}{\max\{1,T-1\}}(\delta-1)+O(\delta)\) vs \(n+\tfrac{n}{\max\{1,T-1\}}(\delta-1)-O(\delta)\) adversarial edge changes

unknown — vs —

Temporal graphs, schedule known

If the whole schedule of an always-connected temporal graph is known, \(\Theta(n^2)\) steps are necessary and sufficient in the worst case.

tight \(O(n^2)\) vs \(\Omega(n^2)\) adversarial edge changes

unknown — vs —

\(T\)-interval-connected graphs, labelled nodes

On a \(T\)-interval-connected graph whose nodes carry identifiers, a deterministic agent can explore every graph with \(m\) edges only if \(T = \Omega(m)\); with a slightly larger window it explores and stops within \(\Theta(n^3)\) moves in the worst case, and within \(\Theta(n^2)\) if it also sees its neighbours' identifiers.

near-optimal \(O((m-n+1)\,n + n\log^2 n)\) vs \(\Omega((m-n+1)\,n)\) adversarial edge changes

unknown — vs —

Open questions 18

Arbitrary graphs, perpetual exploration

What is the time of memory-optimal perpetual exploration, and is there a trade-off between memory and time?

Trees, exploration with stop

Can exploration with stop on trees use asymptotically less memory than exploration with return? (Open problem of Diks et al. 2004.) Equivalently: close \(\Omega(\log\log\log n)\) versus \(O(\log n)\).

Exploration with return and pebbles

How much memory is needed to encode the agent's transition function? The naive table needs \((\log n)^{O(1)}\) bits (Remark 1 of Disser et al. 2019).

Exploration with stop when \(n\) is known

Is \(\Omega(\log n)\) bits necessary when \(n\) is known? The trap arguments Fraigniaud et al. 2005a are stated for agents that know nothing.

Randomized exploration when \(n\) is known

What is the memory needed by a randomized agent that must stop correctly with high probability, as a function of \(n\)?

Exploration with stop and one pebble

Is \(\Omega(D\log\Delta)\) memory needed for exploration with stop by an agent with one pebble Fraigniaud et al. 2005b?

Port numbers chosen by the designer (periodic exploration)

Close the constant gaps: \(2n-2\) versus \(3.5n-2\) for constant memory, \(2.8n - O(1)\) versus \(4n-2\) for oblivious agents Czyzowicz et al. 2012c Kosowski & Navarra 2012.
Trade-offs between period and memory: the only lower bound for agents with memory does not depend on memory.

Directed graphs, one pebble

Close \(\Omega(n\log\Delta_{out})\) versus \(O(n\Delta_{out}\log n)\) bits for exploring digraphs with one pebble.
Determine the trade-off between time and memory: polynomial-time exploration with stop is known only with \(O(n^2\Delta_{out}\log n)\) bits and \(O(\log\log n)\) pebbles, far from the \(\Omega(n\log\Delta_{out})\) lower bound (Section 5 of Fraigniaud & Ilcinkas 2004).

Directed graphs, one pebble, bound on \(n\) known

Improve the \(O(N^2 n^6 \Delta_{out}^2)\) running time (Section 5 of Bender et al. 2002).

Directed graphs with labelled nodes

Close \(\Omega(\phi^2m)\) versus \(O(\phi^8m)\) for online exploration of digraphs with deficiency \(\phi\).

Temporal graphs, schedule known

Tight bounds when the underlying graph is a grid, has bounded degree or is planar Erlebach et al. 2021. For bounded degree and for planar underlying graphs the best bounds known are \(\Omega(n\log n)\) and \(O(n^{3/2}\sqrt{\log n})\) Bastide et al. 2025; the upper bound holds for grids too.
For underlying maximum degree \(\Delta\), close the gap between \(\Omega(\Delta n(1+\log(n/\Delta)))\) Carnevale 2026 and \(O(\min\{n^2, n^{3/2}\sqrt{\Delta\log n}\})\) Bastide et al. 2025; for constant \(\Delta\) the bounds are \(\Omega(n\log n)\) and \(O(n^{3/2}\sqrt{\log n})\). The upper bound needs only that every snapshot has maximum degree at most \(\Delta\).
When at most \(\mu\) edges are missing in each snapshot, remove the factor \(\mu\) between \(O(\mu n\log\mu)\) Lahtin & Zamaraev 2027 and \(\Omega(n\log\mu)\) (as reported by Lahtin & Zamaraev 2027).

\(T\)-interval-connected graphs, labelled nodes

Close the gap on the window, \(\Omega(m)\) against \(O(\zeta m + n\log^2 n)\); it is at most a \(\log^2 n\) factor and remains when \(m = n^{1+o(1)}\) Sudo et al. 2026c.
How much smaller can the window be, and how much faster the exploration, for a randomized agent Sudo et al. 2026c?
Close the polylogarithmic gap on the time with 1-hop view, \(\Omega(m)\) against \(O(\zeta m + n\log^2 n)\), and determine exactly what the 1-hop view buys Sudo et al. 2026c.

What the community started looking at

Exploration began as maze search by finite automata. The first question was whether a machine with bounded memory can visit every node at all: Budach showed it cannot for mazes Budach 1978, Blum and Kozen showed that two pebbles or two automata are enough in mazes Blum & Kozen 1978, and Rollik showed that every finite team has a planar trap Rollik 1980.

From there the community turned to how much memory an agent needs as a function of the graph: \(\Theta(D\log\Delta)\) bits in general Fraigniaud et al. 2005a, \(O(\log n)\) once \(n\) is known Reingold 2008, and the effect of the termination requirement on trees Diks et al. 2004 Ambühl et al. 2011. Markers came next: what one pebble buys Fraigniaud et al. 2006c, and the exact exchange rate between pebbles and memory Disser et al. 2019. Time was a secondary measure throughout.

Derived problems

Treasure hunt: An agent that explores the graph finds any treasure, so every exploration algorithm solves treasure hunt; the question is how much cheaper it can be when the treasure is close, measured against its distance \(d\) (or a weight of the path to it) rather than the size of the graph.

Rendezvous: If the agents can break symmetry (for example by their labels), one may wait while the other explores, so exploration solves rendezvous; the work is in doing better than that, or in meeting when neither knows who should wait Pelc 2019.

Map construction: Building an isomorphic map implies having visited every node, so map construction is exploration with more output; it is used to solve rendezvous and leader election Das 2019.

Exploration by oblivious robots: The robots follow the Look–Compute–Move model of the plane, moved to graphs: they see the positions of all robots but remember nothing, so the configuration itself must encode the progress of the exploration.

Exploration of recolourable graphs: The same task for one agent (visit every node; with return, stop or perpetually), but every node holds a colour from a palette of \(c\) colours that the agent at the node reads and, unless the colours are fixed, overwrites; the agent itself may have no memory at all, and in the main model it has no port numbers and sees its neighbours' colours instead. With \(c = 1\) the colours carry nothing: an algorithm of the parent problem that uses no markers works here whenever this setting grants its ports, entry port and memory, and a lower bound of this problem proved for any number of colours holds for the parent setting with the same view. The parent's pebbles are movable markers carried by the agent Pattanayak & Pelc 2024a Disser et al. 2019; here the marks stay in the nodes and there is one per node.

Online exploration of weighted graphs: The same task for one agent (visit every node and return to the start node), in the tradition of online algorithms: nodes carry identifiers, edges carry weights, memory and computation are unbounded, and an algorithm is judged by its competitive ratio against a shortest tour rather than by its memory. Results do not transfer in either direction without care: the parent counts moves on anonymous unweighted graphs, this problem counts weight on labelled weighted graphs. The setting directed-labelled of the parent Deng & Papadimitriou 1999 is the analogue for unweighted directed graphs.

Collision-free exploration: Every agent explores the graph as in exploration, and no two agents may ever be at the same node. A single-agent exploration procedure is the building block: with vision of radius 2, two agents run any such procedure with a slowdown of at most a factor \(\log n\) Bhagat & Pelc 2025 (a constant factor is claimed by Papin 2026). Lower bounds for exploring by one agent hold here whenever every agent must visit every node.

Perspectives

Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
Finding your way A single agent in an anonymous graph: how much memory it needs, what a pebble, an advice string or knowledge of n buys, why stopping is harder than exploring, and how treasure hunt asks for exploration only as far as the target. Each line of papers, in its own words, on why the question matters.
From exploration to dispersion, and beyond How collaborative exploration asks how much a team speeds up a search, how dispersion arose as the case k = n under weaker assumptions, what dispersion gives back to exploration, and why dispersing first has become the standard opening move for computing graph structures with agents.
What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.
The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.

All settings

The assumption tree (18 settings, 5 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Memory); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Node identifiers › Knowledge › Randomness › Markers › Preprocessing › Termination requirement › Topology.

tight near-optimal polynomial gap unknown impossible no variant

No assumptions · 2 branches by graph dynamics Nothing is assumed on any axis.
- +static graph
  Edge direction · 4 branches
  - +undirected
    Knowledge · 8 branches
    - nothing knownno markersadversarial ports+perpetual
      Arbitrary graphs, perpetual exploration standard setting The classical memory question: how many bits must a finite-state agent have to visit every node of every graph of diameter \(D\) and degree \(\Delta\)?
      - +tree
        Trees, perpetual exploration On trees, perpetual exploration needs exactly \(\Theta(\log\Delta)\) bits: enough to remember a port.
    - nothing knownno markersadversarial ports+with stop
      Exploration with stop, nothing known Without a bound on \(n\) and without a way to mark a node, an agent can never be sure it has seen everything.
      - +tree
        Trees, exploration with stop Stopping on a tree without knowing \(n\) needs more than constant memory, but how much more is open: \(\Omega(\log\log\log n)\) against \(O(\log n)\).
    - nothing known+pebbles
      Exploration with return and pebbles \(\Theta(\log\log n)\) pebbles are necessary and sufficient for a constant-memory agent, which then explores in polynomial time and returns to the start without knowing \(n\).
      - +perpetual
        Memoryless automaton with pebbles A deterministic memoryless automaton (one state) explores every connected graph with 2 pebbles, and 2 is the minimum.
    - +knows a bound on \(n\)
      Randomness · 2 branches
      - deterministic+with stop
        Exploration with stop when \(n\) is known Reingold's log-space universal exploration sequences give an \(O(\log n)\)-bit agent that explores and stops in polynomial time.
      - +private coins+with stop
        Randomized exploration when \(n\) is known A random walk covers any graph in expected \(2m(n-1)\) steps; with a step counter and a bound on \(n\) it stops after exploring with good probability.
    - nothing known+one pebble+with stop
      Exploration with stop and one pebble One pebble makes stopping possible; the agent then needs \(\Omega(\log n)\) bits.
    - nothing knownno markersadversarial portswith return+tree
      Trees, exploration with return Returning to the start on a tree takes \(\Theta(\log n)\) bits.
    - nothing knownno markers+designer labels+with stop
      Node labels chosen by the designer With three-valued labels on the nodes, an agent with fewer than 25 states explores every graph and stops after at most \(20m\) edge traversals.
    - nothing knownno markers+designer ports+perpetual
      Port numbers chosen by the designer (periodic exploration) If the designer may set the port numbers, a constant-memory agent visits every node periodically with period between \(2n-2\) and \(3.5n-2\).
  - directedanonymous nodesnothing known+one pebble+with stop
    Directed graphs, one pebble An agent that cannot walk back along an arc needs \(\Omega(n\log\Delta_{out})\) bits, even with up to \(n\) pebbles; with one pebble, \(O(n\Delta_{out}\log n)\) bits suffice, in exponential time.
  - directedanonymous nodes+knows a bound on \(n\)+one pebble+with stop
    Directed graphs, one pebble, bound on \(n\) known With a bound \(N \ge n\), one pebble lets an agent map any strongly connected digraph in polynomial time.
  - directed+labelled nodes+with stop
    Directed graphs with labelled nodes draft An agent that recognises nodes but cannot backtrack must traverse every arc; the cost depends on the deficiency \(\phi\) of the digraph.
- +connected every round+undirected
  Node identifiers · 3 branches

Assumptions specific to this problem

Knowledge

0nothing known about the graph1an upper bound on \(n\) is known2a complete map is known (for a dynamic graph: the whole schedule)

Knowing the size of the graph is the classical way to let an exploring walk end. Aleliunas, Karp, Lipton, Lovász and Rackoff proved that a random walk on a connected graph visits every node within \(2m(n-1)\) expected steps from any start (Theorem 4), so by Markov's inequality \(O(mn\log n)\subseteq O(n^3\log n)\) steps cover it with high probability, and a step counter and the value of \(n\) give a randomized explorer that stops Aleliunas et al. 1979; Reingold's log-space universal exploration sequences do the same deterministically when \(n\) is known Reingold 2008 (Corollary 5.5). Without a bound and without a marker an agent cannot tell a cycle from a longer one, so it can explore perpetually but never stop Fraigniaud et al. 2006c. Bender, Fernández, Ron, Sahai and Vadhan measured what the bound is worth in directed graphs: one pebble suffices when an upper bound on \(n\) is known, while without it \(\Theta(\log\log n)\) pebbles are necessary and sufficient, the lower bound holding even for randomized robots Bender et al. 2002. The top level, a full map, makes static exploration an offline planning task (a known undirected graph is explored by depth-first search in fewer than \(2n\) steps); it matters for temporal graphs, where exploration with the whole schedule known in advance was introduced by Michail and Spirakis, who are given the whole temporal graph as input and show that the fastest exploration cannot be approximated within \(cn\) for some constant \(c > 0\) unless P = NP (Theorem 1) Michail & Spirakis 2016, and studied by Erlebach, Hoffmann and Kammer Erlebach et al. 2021.

Formal definitions

0nothing known: The agent knows nothing about \(G\): not \(n\), \(m\), \(\Delta\) or \(D\).
1knows a bound on \(n\): The agent is given an integer \(N\ge n\) (an upper bound on the number of nodes) as input.
2knows the map: The agent is given a graph isomorphic to \(G\), with port numbers, and (where stated) its own position on it; for a dynamic graph, the whole sequence \((G_t)\).

Markers

0no markers1one pebble (a movable marker)2several pebbles; their number is a resource

Pebbles come from the tradition of automata in mazes. After Budach proved that no finite automaton explores every finite maze Budach 1978, Blum and Kozen showed that two pebbles suffice for a finite automaton in a maze, against Shah's conjecture that five were needed, and left open whether one pebble suffices Blum & Kozen 1978; Hoffmann showed that it does not (as cited by Disser et al. 2019). Cohen, Fraigniaud, Ilcinkas, Korman and Peleg describe this "Rabin's pebble model" as the ability of the robot to label nodes dynamically, at most one unit of label per pebble Cohen et al. 2008. Bender et al. carried the question to directed graphs and agents with unbounded memory, titling their paper "The power of a pebble": one pebble and a bound on \(n\) already give polynomial-time mapping Bender et al. 2002. In anonymous graphs a marker is what makes stopping possible at all, and by convention a robot asked to stop is given a pebble Fraigniaud et al. 2006c. The number of pebbles became a resource of its own when Disser, Hackfeld and Klimm showed that \(\Theta(\log\log n)\) pebbles are necessary and sufficient for a constant-memory agent on undirected graphs, and that an agent with \(O((\log n)^{1-\varepsilon})\) bits already needs \(\Omega(\log\log n)\) of them Disser et al. 2019; this is why one pebble and several pebbles are separate levels.

Formal definitions

0no markers: The agent cannot mark nodes.
1one pebble: The agent carries one pebble that it can drop at its current node and later pick up; it sees whether a pebble is at its node.
2pebbles: The agent carries \(p\) pebbles (identical or distinguishable, as stated); \(p\) is a resource reported with the memory.

Preprocessing

0ports and nodes as given by an adversary1port numbers chosen by the designer1short node labels chosen by the designer

This axis asks what a designer who prepares the graph before the agent arrives can do for it, a question that grew out of the impossibility results of Budach and Rollik for finite automata Budach 1978 Rollik 1980. Cohen, Fraigniaud, Ilcinkas, Korman and Peleg let the designer write short labels on the nodes and showed that three label values let a constant-memory robot explore every graph and stop; by Rollik's result two values are the minimum one could hope for Cohen et al. 2008. They place the model next to pebbles: it "can be considered stronger than Rabin's pebble model since labels are given in a preprocessing stage, but it can also be considered weaker since, once assigned to nodes, the labels cannot be modified", and they cite it as part of a line of work on short information supplied in advance, including the oracle-size measure of Fraigniaud, Ilcinkas and Pelc Cohen et al. 2008 Fraigniaud et al. 2006b. Choosing the port numbers is preprocessing that writes nothing on the nodes: Ilcinkas starts from Budach's result that no finite automaton explores all graphs when an adversary sets the local orientation, and asks for the shortest exploration period when the designer sets it, improving the period \(10n\) of Dobrev et al. to \(4n\) Ilcinkas 2008. The two forms of preprocessing are kept on the same level because neither is known to simulate the other.

Formal definitions

0adversarial ports: Port numbers (and any node labels) are chosen by an adversary.
1designer ports: Before the agent starts, the designer may choose the port numbering \(\mathrm{port}_v:\{\text{edges at }v\}\to\{1,\dots,\deg(v)\}\) at every node. Ilcinkas calls a designer's port numbering a local orientation Ilcinkas 2008.
1designer labels: Before the agent starts, the designer may write a label of \(b\) bits (a constant) at every node, which the agent reads on arrival.

Termination requirement

0explore, then stop at the start node1explore, then stop anywhere2visit every node; never required to stop (perpetual)

The three termination requirements were separated in the memory-bounded exploration literature of the early 2000s. Fraigniaud, Ilcinkas, Peer, Pelc and Peleg list them explicitly, exploration with return, exploration with stop and perpetual exploration, and recall that Diks, Fraigniaud, Kranakis and Pelc showed for trees that exploration with stop needs \(\Omega(\log\log\log n)\) bits of memory Fraigniaud et al. 2005a Diks et al. 2004; the same paper shows that exploration with return needs \(\Omega(\log n)\) bits Diks et al. 2004 (as summarised in Disser et al. 2019 and Czyzowicz et al. 2012c), while perpetual exploration of bounded-degree trees is possible with \(O(1)\) bits Fraigniaud et al. 2006c. In arbitrary anonymous graphs the requirement also decides feasibility: a robot cannot recognise that it has closed a cycle, so without a marker or a bound on \(n\) it can explore perpetually but never stop Fraigniaud et al. 2006c. The axis orders the requirements from the hardest (return) to the weakest (perpetual); periodic exploration, which asks every node to be visited infinitely often within a bounded period, is a perpetual task measured by its period Ilcinkas 2008.

Formal definitions

0with return: The agent visits every node and then halts at its start node \(s\).
1with stop: The agent visits every node and then halts, at any node. Also called terminating exploration.
2perpetual: Every node is visited at least once (and, for periodic exploration, infinitely often); the agent never needs to halt.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.

Graph exploration by a single agent

A first look

What is known

Open questions 18

Arbitrary graphs, perpetual exploration

Trees, exploration with stop

Exploration with return and pebbles

Exploration with stop when \(n\) is known

Randomized exploration when \(n\) is known

Exploration with stop and one pebble

Port numbers chosen by the designer (periodic exploration)

Directed graphs, one pebble

Directed graphs, one pebble, bound on \(n\) known

Directed graphs with labelled nodes

Temporal graphs, schedule known

\(T\)-interval-connected graphs, labelled nodes

What the community started looking at

Derived problems

Related problems

Perspectives

Further reading

All settings

Assumptions specific to this problem

Knowledge

Markers

Preprocessing

Termination requirement