Graph exploration by a single agent

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 (as summarised in Disser et al. 2019). 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. 2006. 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 Michail & Spirakis 2016 (as reported by Erlebach et al. 2021) and studied by Erlebach, Hoffmann and Kammer Erlebach et al. 2021.

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. 2006. 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.

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. 2006. 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.

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. 2005 Diks et al. 2002; the same paper shows that exploration with return needs \(\Omega(\log n)\) bits Diks et al. 2002 (as summarised in Disser et al. 2019 and Czyzowicz et al. 2012), while perpetual exploration of bounded-degree trees is possible with \(O(1)\) bits Fraigniaud et al. 2006. 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. 2006. 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.