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.
\(T\)-interval-connected graphs, labelled nodes
verifiedOn 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.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: connected every round
- \(\mathcal G=(G_t)_{t\ge0}\) is 1-interval connected if every snapshot \(G_t=(V,E_t)\) is connected. More generally it is \(T\)-interval connected if for every \(t\) the graph \(\bigl(V,\bigcap_{i=t}^{t+T-1}E_i\bigr)\) is connected.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- 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.
Statement for this variant
The graph is a dynamic graph \((G_t)_{t \ge 0}\) on a fixed node set; its underlying graph (all edges that ever appear) is simple and connected, with \(n\) nodes and \(m \ge n\) edges. It is \(T\)-interval connected: for every \(t\), the edges present in all of the rounds \(t, \dots, t+T-1\) form a connected spanning subgraph. Every node carries a distinct identifier. In round \(t\) the agent at node \(v\) sees the identifier of \(v\), \(\deg(v)\) in the underlying graph, which ports of \(v\) have their edge present in \(G_t\), and the port by which it entered; it then crosses one present edge or stops (staying put only uses up the window). The agent is deterministic and knows neither \(T\), \(n\) nor \(m\); it must visit every node and stop. Two quantities are asked for: the smallest window \(T\), as a function of \(n\) and \(m\), for which some algorithm explores every \(T\)-interval-connected graph, and the number of moves it then needs. With 1-hop view (the model KT\(_1\) of Sudo et al. 2026c; the setting above is their KT\(_0\)) the agent also sees the identifiers of its neighbours in \(G_t\) and the ports that lead to them.
What is known
- deterministic agent that sees only its own node (KT\(_0\)); \(n\) large enough and \(n \le m \le \binom n2\)
- holds for every window \(T\): a spanning path is present in every round (\(\infty\)-interval connected)
- the underlying graph is a path \(v_1, \dots, v_n\), plus \(\min(m-n+1, |V_L|\,|V_R|)\) trap edges between \(V_L\) (the first third of the path) and \(V_R\) (its last third without \(v_n\)), plus edges that are never present while the agent is at one of their ends; the agent starts at \(v_1\)
- the adversary removes the trap edges at every node of \(V_L\) the agent visits, and, since the agent learns where a port leads only by crossing its edge, sends every unused port of a node of \(V_R\) along an unused trap edge
- window \(T \le \kappa m\) for a small enough constant \(\kappa > 0\) (Theorem 3): for every \(n\) large enough and every \(m\) with \(n \le m \le \binom n2\), some \(T\)-interval-connected graph with \(n\) nodes and \(m\) edges has a node that the agent never visits
- deterministic agent; holds with 1-hop view and even for perpetual exploration
- for \(m \ge 2n\): two copies of \(K_g\) minus one edge, \(g = \lfloor\sqrt{m/8}\rfloor\), joined through three nodes and one edge, with a path attached; an agent that enters a copy can be kept inside it for \(\Omega(g^2)\) rounds without disconnecting any window (Lemma 9, which holds even if the agent knows the underlying graph with its ports)
- for \(n \le m < 2n\): a ring whose two edges at one node are removed alternately, which keeps the graph \((n-3)\)-interval connected
- with 1-hop view (KT\(_1\)); deterministic agent
- holds for every window \(T\) (\(\infty\)-interval connected)
- a path of \(n-g\) nodes attached to \(K_g\) minus one edge, \(g = \lfloor\sqrt m\rfloor\); the agent starts inside the \(K_g\) part and is kept there for \(\Omega(g^2)\) rounds (Lemma 9)
Results, in order of publication
Introductory and current best (Theorem 1, algorithm GreedyExp\(_0\); \(\zeta\) is their \(\epsilon(n,m)\)). The agent walks, along edges it has never seen missing, to the nearest visited node that has an unused port whose edge was present at every visit, and crosses that edge. Every \(\kappa(\zeta m' + n'\log^2 n')\) moves, with \(n'\) and \(m'\) computed from the nodes and ports seen so far, it forgets which edges it saw missing, so that each such period has a spanning tree present throughout. A period that does not end the exploration contains at least \(\kappa(\zeta m' + n'\log^2 n')/(2n')\) crossings of unused edges into visited nodes (Lemma 8), and there are at most \(m-n+1\) such crossings (Corollary 4).
Theorem 2, algorithm GreedyExp\(_1\): walk to the nearest node seen but not visited, in the map of edges never seen missing. Exploration ends within the window itself, so one spanning tree is present throughout. The distance to the nearest unvisited node grows by at most \(2n\log n\) in total when new nodes are visited (Lemma 4) and by \(O(\zeta m + n\log^2 n)\) when edges are seen missing, through the bound \(|E| \le \tfrac12|V|^{1+1/j} + \tfrac12|V|\) for graphs of girth at least \(2j+1\) (Lemmas 5 and 6).
Open questions
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.
Notes
Sudo, Kitamura, Shibata, Nakamura, Tixeuil, Masuzawa and Wada study a single deterministic agent on \(T\)-interval-connected graphs of arbitrary topology Sudo et al. 2026c. They assume \(m \ge n\), since with \(m = n-1\) every edge is always present and the graph is static. Their lower bounds on time hold even if one spanning tree is present forever: the cost comes from edges that are absent while the agent stands at one of their ends, not from disconnection. On rings the window has to be large as well (the case \(m < 2n\) of Theorem 3); this is why the online exploration of \(T\)-interval-connected rings Ilcinkas & Wade 2018 also assumes that every edge appears at least once in every \(\delta\) consecutive rounds, as Sudo et al. recall. Both algorithms rely on the identifiers: the agent recognises the nodes it has visited and keeps a map of the edges it has seen. Checked against the full text (arXiv v1, 2026), a preprint.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.