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 measuresexpand
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.
Directed graphs with labelled nodes
draftAn agent that recognises nodes but cannot backtrack must traverse every arc; the cost depends on the deficiency \(\phi\) of the digraph.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: directed
- \(G=(V,A)\) with \(A\subseteq V\times V\); an agent at \(u\) may move along \((u,v)\in A\) only, never back along it unless \((v,u)\in A\). \(G\) is strongly connected.
- Node identifiers: labelled nodes
- Each node \(v\) carries a distinct identifier that agents at \(v\) can read; hence an agent can recognise a node it has visited.
- Knowledge: nothing known
- The agent knows nothing about \(G\): not \(n\), \(m\), \(\Delta\) or \(D\).
- Randomness: deterministic
- The next state and move of an agent are a function of its current state and what it observes.
- Markers: no markers
- The agent cannot mark nodes.
- Preprocessing: adversarial ports
- Port numbers (and any node labels) are chosen by an adversary.
- Termination requirement: with stop
- The agent visits every node and then halts, at any node. Also called terminating exploration.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
- deficiency \(\phi\): the number of arcs to add to make the digraph Eulerian
- deterministic strategies; the argument does not apply to randomized ones
- due to Koutsoupias: Corollary 3 of Deng & Papadimitriou 1999 gives at least \(\phi^2/4\) times the number of arcs
Results, in order of publication
Theorem 3: no arc is traversed more than \(2^{O(\phi\log\phi)}\) times, without knowing \(\phi\). Eulerian digraphs (\(\phi=0\)): ratio 2 to the optimal tour, which is optimal; deficiency one: no arc traversed more than four times (Theorem 2).
First subexponential algorithm; the authors also show that their algorithm needs \(\phi^{\Omega(\log\phi)}m\) on some graphs, and that Greedy, Depth-First and Breadth-First need \(2^{\Omega(\phi)}m\).
First algorithm polynomial in \(\phi\); the paper itself was not read, the bound is from the authors' abstract.
Open questions
Close \(\Omega(\phi^2m)\) versus \(O(\phi^8m)\) for online exploration of digraphs with deficiency \(\phi\).
Notes
This is the online-algorithms tradition: nodes are recognisable and the agent builds a map; cost is compared with the optimal tour (the Chinese postman tour), and Deng and Papadimitriou note that measured in absolute terms \(\Theta(nm)\) is trivially tight. Checked against the full texts of Deng & Papadimitriou 1999 and Albers & Henzinger 2000; the bound of Fleischer & Trippen 2005 is still from the authors' abstract.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.