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.
Port numbers chosen by the designer (periodic exploration)
draftIf the designer may set the port numbers, a constant-memory agent visits every node periodically with period between \(2n-2\) and \(3.5n-2\).
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: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Node identifiers: anonymous nodes
- Nodes have no identifiers; an agent at \(v\) sees only \(\deg(v)\) and the port numbers \(1,\dots,\deg(v)\), which are assigned locally and independently at each endpoint of an edge.
- 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: designer 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.
- Termination requirement: perpetual
- Every node is visited at least once (and, for periodic exploration, infinitely often); the agent never needs to halt.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
- any agent: on a tree every edge is traversed in both directions
- realised by the star; folklore
- for oblivious agents the bound is \(2.8n-2\)
Results, in order of publication
Theorem 1; the abstract rounds the period to \(4n\).
The step between \(4n-2\) and \(3.5n-2\), as cited by Czyzowicz et al. 2012.
For oblivious agents the same paper gives \((4+\tfrac13)n-4\); the best oblivious period is \(4n-2\) Kosowski & Navarra 2012.
Figure as reported by Czyzowicz et al. 2012.
Open questions
Close the constant gaps: \(2n-2\) versus \(3.5n-2\) for constant memory, \(2.8n-2\) versus \(4n-2\) for oblivious agents Czyzowicz et al. 2012.
Trade-offs between period and memory: the only lower bound for agents with memory does not depend on memory.
Notes
Without the designer's help, periodic exploration by a finite automaton is impossible (Budach, as cited by Czyzowicz et al. 2012). These papers began with Dobrev, Jansson, Sadakane and Sung (SIROCCO 2005; period \(10n\), as cited by Czyzowicz et al. 2012). Computing the shortest witness cycle for an oblivious agent is NP-hard. The period is defined differently: Ilcinkas counts returns to a node in the same state through the same port, Czyzowicz et al. returns to a node through the same port. Unverified: the oblivious \(4n-2\) of Kosowski & Navarra 2012, known only from Czyzowicz et al. 2012.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.