Mobility Matters
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 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.

no assumptions›+ static graph›+ undirected›nothing known, + one pebble, + with stop

Exploration with stop and one pebble

verified
Time: unknownMemory: polynomial gap

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

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Markersone pebble (a movable marker)+Termination requirementexplore, then stop anywhere

Not assumed

Node identifiersanonymous nodesKnowledgenothing known about the graphRandomnessdeterministicPreprocessingports and nodes as given by an adversaryTopologyarbitrary connected graph
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: one 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.
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

Time · edge traversals until every node is visited (for periodic exploration: the period)
unknown
Time not studied.
lower boundnone known
introductory—
current best—
Memory · bits of agent memory; pebbles, if any, are counted separately
polynomial gap
\(O(D\log\Delta)\) versus \(\Omega(\log n)\): polynomial when \(D\) is large.
lower bound
\(\Omega(\log n)\) Fraigniaud et al. 2006
bottleneckreduced automata
holds when
  • deterministic agent with one pebble that starts on the agent's start node
  • no knowledge of \(n\)
  • the traps are edge-coloured regular graphs of size \(O(K^3)\) for a \(K\)-state agent (Theorem 5 of Fraigniaud et al. 2006)
introductory—
current best
\(O(D\log\Delta)\)

Results, in order of publication

Fraigniaud et al. 2005 current best
Memory \(O(D\log\Delta)\)

Introductory and current best (Theorem 3, DFS-with-stop): the pebble marks the start; depth-first phases of depth \(1, 2, \dots\) detect new nodes, and the agent stops after phase \(D+1\). No knowledge of \(D\) or \(\Delta\). Time is not analysed.

Open questions

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

Notes

The same authors show that \(k\) non-cooperative agents need \(\Omega(\log(n/k))\) bits for perpetual exploration, with traps of size \(O(kK)\) Fraigniaud et al. 2006. That chapter is inconsistent on tightness: a remark calls the \(\Omega(\log n)\) bound tight, citing the SIROCCO paper, while its conclusion says a tight bound for terminating exploration is open. Checked against the full texts.

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

Exploration with stop, nothing known
Directed graphs, one pebble
Memory \(O(n\Delta_{out}\log n)\)

Lower bounds from stronger settings hold here

Memoryless automaton with pebbles
Memory \(2\ \text{pebbles}\)

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