# Efficient Exploration of Anonymous Undirected Graphs

Ralf Klasing

► To cite this version:

Ralf Klasing. Efficient Exploration of Anonymous Undirected Graphs. Proceedings of the 24th International Workshop on Combinatorial Algorithms (IWOCA 2013), Jul 2013, Rouen, France. pp.7-13, 10.1007/978-3-642-45278-9_2. hal-00927154

HAL Id: hal-00927154

https://hal.science/hal-00927154v1

Submitted on 7 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Efficient Exploration of Anonymous
Undirected Graphs*

Ralf Klasing

CNRS - LaBRI - Université de Bordeaux
351 cours de la Libération, 33405 Talence, France
klasing@labri.fr

**Abstract.** We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information. In this paper, we present some current developments in the area. In particular, we focus on recent work on *equitable strategies* and on the *multi-agent rotor-router*.

# 1 Introduction

A widely studied problem concerns the exploration of an anonymous graph $G = (V, E)$, with the goal of visiting all its vertices and regularly traversing its edges. At each discrete moment of time, the robot is located at a node of the graph, and is provided with only a local view of the adjacent edges of the graph.

The *random walk* is an oblivious exploration strategy in which the edge used by the robot to exit its current location is chosen with equal probability from among all the edges adjacent to the current node; cf. e.g. [2,21] for an extensive introduction to the topic. A recently proposed deterministic counterpart of the random walk is the *rotor-router model* [24] (a.k.a. the *Propp machine* or the *Edge Ant Walk* [26,27]), which requires some (small) memory at the nodes of the graph. An alternative deterministic traversal method is the *basic walk*, in which a small amount of memory is provided to an agent and a certain type of graph preprocessing is permitted; cf. e.g. [10, 14, 20] for some recent papers on the latter topic. An extensive survey on graph exploration using the *random walk*, the *rotor-router* and the *basic walk* can be found in [15].

In this paper, we present some current developments in the area of memory efficient exploration of anonymous graphs. In particular, we focus on recent work on *equitable strategies*, in which the environment attempts to mimic the fairness properties of the random walk with respect to the use of edges, and on the *multi-agent rotor-router*, i.e., a rotor-router system in which more than one agent are deployed in the same environment.

<footnote>* The research was partially funded by the ANR project "DISPLEXITY".</footnote>
## 2 Locally Fair Exploration Strategies

The exploration strategies studied in this section fall into the line of research devoted to derandomizing random walks in graphs [7, 11, 26, 27].

Explorations achieved through random walks are on average good, in the sense that the following properties hold in expectation:

(1) Within polynomial time, the walk visits all of the vertices of the graph.

(2) Within polynomial time, the walk stabilizes to the steady state, and henceforth all edges are visited with the same frequency.

We focus on the problem of designing local exploration strategies which derandomize a random walk in a graph in an attempt to achieve the above stated properties in the deterministic sense of worst-case performance. The next vertex to be visited should depend only on the values of certain parameters associated with the edges adjacent to the current node. Such a problem naturally gives rise to the definition of locally equitable strategies, i.e. strategies, in which at each step the robot chooses from among the adjacent edges the edge which is in some sense the “poorest”, in an effort to make the traversal fair. In this context, two natural notions of equity may be defined:

- An exploration is said to follow the *Oldest-First (OF)* strategy if it directs the robot to an unexplored neighboring edge, if one exists, and otherwise to the neighboring edge for which the most time has elapsed since its last traversal, i.e. the edge which has waited the longest.

- An exploration is said to follow the *Least-Used-First (LUF)* strategy if it directs the robot to a neighboring edge which has so far been visited by the robot the smallest number of times.

When the considered graph is symmetric and directed, and the above definitions are applied to directed edges, then the Oldest-First notion of equity is known to be strictly stronger than Least-Used-First, i.e. any exploration which follows the OF strategy also follows the LUF strategy [27]. Moreover, the Oldest-First strategy is in this context equivalent to the well-established efficient exploration model based on the rotor-router model. In the directed case, both of the described locally fair exploration strategies are known to preserve properties (1) and (2) of the random walk. More precisely, for a symmetric directed graph of diameter *D*, any exploration which follows such a strategy achieves a *cover time* (i.e., the time until all nodes have been visited at least once) of $O(D|E|)$ and stabilizes to a globally fair traversal of all the edges. When the Oldest-First and Least-Used-First strategies are applied to the *undirected* edges of a graph, the results, and the used techniques, turn out to be surprisingly different. More precisely, [8] establishes the following properties of explorations which follow the Oldest-First or Least-Used-First strategies in undirected graphs.

*The Oldest-First (OF) strategy* in undirected graphs can be regarded as a natural analogue of the Oldest-First strategy (rotor-router model) for symmetric directed graphs. However, whereas the rotor-router model leads to explorations which
traverse directed edges with equal frequency, and have a cover time bounded by $O(D|E|)$, this is not the case for Oldest-First explorations in undirected graphs. Indeed, [8] shows the following theorems.

- In some classes of undirected graphs, any exploration which follows the Oldest-First strategy is unfair, with an exponentially large ratio of visits between the most often and least often visited edges.

- There exist explorations following the Oldest-First strategy which have exponential cover time of $2^{\Omega(|V|)}$ in some graph classes.

The Least-Used-First (LUF) strategy in undirected graphs is fundamentally better than the Oldest-First strategy, which is contrary to the situation in symmetric directed graphs. In fact, [8] shows that, in undirected graphs, explorations which follow the LUF strategy are fair, efficient, and tolerant to perturbations of initial conditions, as expressed by the following theorems.

- Any exploration of an undirected graph which follows the Least-Used-First strategy is fair, achieving uniform distribution of visits to all edges.

- Any exploration of an undirected graph which follows the Least-Used-First strategy achieves a cover time of $O(D|E|)$, where $D$ denotes the diameter. This bound is tight. When the exploration starts from a state with non-zero (corrupted) initial values of traversal counts on edges, the cover time is bounded by $O((|V| + p)|E|)$, where $p$ is the maximal value of a counter in the initial state.

Strategies with local equity criteria have also been studied in the token circulation literature, in the context of strategies which are locally fair to vertices rather than edges. Two such strategies, named LF and LR, were proposed and analyzed in [22]. In the first of these, LF, the next vertex to be visited is always chosen as the least-often visited neighbor of the current vertex. In the second, LR, the next vertex to be visited is the neighbor which has not been visited for the longest time. The authors of [22] show that both of these strategies eventually visit all vertices, but in general do not satisfy any fairness criteria. Indeed, the time between successive visits to a vertex may be exponential in the order of the graph for LR, and unbounded for LF. In this sense, the results of [22] may be contrasted with the results of [8] for the LUF strategy.

## 3 The Multi-agent Rotor-Router

The study of deterministic exploration strategies in agent-based models of computation is largely inspired by considerations of random walk processes. For an undirected graph $G = (V, E)$, exploration with the random walk has many advantageous properties: the expected arrival time of the agent at the last unvisited node of the graph, known as the *cover time* $C(G)$, can in general be bounded as, e.g., $C(G) \in O(D|E| \log |V|)$, where $D$ is the diameter of the graph. The random walk also has the property that in the limit it visits all of the edges of the graph with the same frequency, on average, traversing each once every
$|E|$ rounds. The rotor-router model, introduced by Priezzhev et al. [24] and further popularised by James Propp, provides a mechanism for the environment to control the movement of the agent deterministically, whilst retaining similar properties of exploration as the random walk.

In the rotor-router model, the agent has no operational memory and the whole routing mechanism is provided within the environment. The edges outgoing from each node $v$ are arranged in a fixed cyclic order known as a *port ordering*, which does not change during the exploration. Each node $v$ maintains a *pointer* which indicates the edge to be traversed by the agent during its next visit to $v$. If the agent has not visited node $v$ yet, then the pointer points to an arbitrary edge adjacent to $v$. The next time when the agent enters node $v$, it is directed along the edge indicated by the pointer, which is then advanced to the next edge in the cyclic order of the edges adjacent to $v$.

The behavior of the rotor-router for a single agent is well understood. Yanovski et al. [27] showed that, regardless of the initialization of the system, the agent stabilizes to a traversal of a directed Eulerian cycle (containing all of the edges of the graph) within $2D|E|$ steps. A complementary lower bound was provided by Bampas et al. [4], who showed that for any graph there exists an initialization of the system for which covering all the nodes of the graph and entering the Eulerian cycle takes $\Theta(D|E|)$ steps. Robustness properties of the rotor-router were further studied in [5], who considered the time required for the rotor-router to stabilize to a (new) Eulerian cycle after an edge is added or removed from the graph.

[18, 27] consider the setting in which multiple, indistinguishable agents are deployed in parallel in the nodes of the graph, and move around the graph in synchronous rounds, interacting with a single rotor-router system. Yanovski et al. [27] showed that adding a new agent to the system cannot slow down exploration, and provided some experimental evidence showing a nearly-linear speed-up of cover time with respect to the number of agents in practical scenarios. They also show that the multi-agent rotor-router eventually visits all edges of the graph a similar number of times. In [18], new techniques are proposed which allow to perform a theoretical analysis of the multi-agent rotor-router model, and to compare it to the scenario of parallel independent random walks in a graph [3, 12, 13, 25]. The main results concern the $n$-node ring, and suggest a strong similarity between the performance characteristics of this deterministic model and random walks.

More precisely, it is shown that on the ring the rotor-router with $k$ agents admits a cover time of between $\Theta(n^2/k^2)$ in the best case and $\Theta(n^2/\log k)$ in the worst case, depending on the initial locations of the agents, and that both these bounds are tight. The corresponding expected value of cover time for $k$ random walks, depending on the initial locations of the walkers, is proven to belong to a similar range, namely between $\Theta(n^2/(k^2/\log^2 k))$ and $\Theta(n^2/\log k)$.

In addition, the limit behavior of the rotor-router system is studied. It is shown that, once the rotor-router system has stabilized, all the nodes of the ring are always visited by some agent every $\Theta(n/k)$ steps, regardless of how the
system was initialized. This asymptotic bound corresponds to the expected time between successive visits to a node in the case of $k$ random walks. All the results hold up to a polynomially large number of agents ($1 \le k < n^{1/11}$).

A variant of the multi-agent rotor-router mechanism has been extensively studied in a different setting, in the context of balancing the workload in a network. The single agent is replaced with a number of agents, referred to as *tokens*. Cooper and Spencer [9] study $d$-dimensional grid graphs and show a constant bound on the difference between the number of tokens at a given node $v$ in the rotor-router model and the expected number of tokens at $v$ in the random-walk model. Subsequently, Doerr and Friedrich [11] analyse in more detail the distribution of tokens in the rotor-router mechanism on the 2-dimensional grid. Recent work on the multi-agent rotor-router mechanism for balancing the workload in a network comprises e.g. [1, 17].

# 4 Conclusion and Future Work

In Section 2, we have seen that locally fair strategies in undirected graphs can closely imitate random walks, allowing to obtain an exploration which is fair with respect to all edges, and efficient in terms of cover time. However, the fairness criterion has to be chosen much more carefully than for symmetric directed graphs: Least-Used-First works, but Oldest-First does not.

In future work it would be interesting to study modified notions of equity, which are inspired by random walks which select the next edge to be traversed with non-uniform probability. For example, it is possible to decrease the general-case bound on the cover time of a random walk to $O(|V|^2 \log |V|)$, by applying a probability distribution which reflects the degrees of the nearest neighbors of the current node [16, 19, 23]. It is an open question whether a similar bound can be obtained in the deterministic sense using a derandomized strategy. A somewhat different approach was adopted by Berenbrink et al. [6], who show that a random walk with the additional capability of marking one unvisited node in its neighborhood as visited can be used to speed up exploration. It is an open problem whether a similar speedup can be obtained using a derandomized strategy.

In Section 3, we have seen that the multi-agent rotor-router and the parallel random walk have similar speed-up characteristics w.r.t. the number of deployed agents, at least in terms of cover time and return time on the ring. It is interesting to note that the worst-case speed-up on the ring is $\Theta(\log k)$ for both the $k$-agent random walk and the $k$-agent rotor-router, even though this speed up has a different explanation in both cases. For the random walk, it is a consequence of the properties of probability distributions of independent Markovian processes, while for the rotor-router, it results directly from the interactions between different agents and the pointers in the graph.

This work may also be seen as a step in the direction of understanding and characterizing the behavior of the multi-agent rotor-router in graphs different from the ring. Some of the techniques developed in [18], in particular analysis based on delayed deployments, are also applicable in the general case.
References

1. Akbari, H., Berenbrink, P.: Parallel rotor walks on finite graphs and applications in discrete load balancing. In: SPAA, pp. 186–195 (2013)

2. Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs (2001), http://stat-www.berkeley.edu/users/aldous/RWG/book.html

3. Alon, N., Avin, C., Koucký, M., Kozma, G., Lotker, Z., Tuttle, M.R.: Many random walks are faster than one. Combinatorics, Probability & Computing 20(4), 481–502 (2011)

4. Bampas, E., Gąsieniec, L., Hanusse, N., Ilcinkas, D., Klasing, R., Kosowski, A.: Euler tour lock-in problem in the rotor-router model. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 423–435. Springer, Heidelberg (2009)

5. Bampas, E., Gasieniec, L., Klasing, R., Kosowski, A., Radzik, T.: Robustness of the rotor-router mechanism. In: Abdelzaher, T., Raynal, M., Santoro, N. (eds.) OPODIS 2009. LNCS, vol. 5923, pp. 345–358. Springer, Heidelberg (2009)

6. Berenbrink, P., Cooper, C., Elsässer, R., Radzik, T., Sauerwald, T.: Speeding up random walks with neighborhood exploration. In: SODA, pp. 1422–1435 (2010)

7. Bhatt, S.N., Even, S., Greenberg, D.S., Tayar, R.: Traversing directed eulerian mazes. Journal of Graph Algorithms and Applications 6(2), 157–173 (2002)

8. Cooper, C., Ilcinkas, D., Klasing, R., Kosowski, A.: Derandomizing random walks in undirected graphs using locally fair exploration strategies. Distributed Computing 24(2), 91–99 (2011)

9. Cooper, J.N., Spencer, J.: Simulating a random walk with constant error. Combinatorics, Probability & Computing 15(6), 815–822 (2006)

10. Czyzowicz, J., Dobrev, S., Gasieniec, L., Ilcinkas, D., Jansson, J., Klasing, R., Lignos, I., Martin, R., Sadakane, K., Sung, W.-K.: More efficient periodic traversal in anonymous undirected graphs. Theoretical Computer Science 444, 60–76 (2012)

11. Doerr, B., Friedrich, T.: Deterministic random walks on the two-dimensional grid. Combinatorics, Probability & Computing 18(1-2), 123–144 (2009)

12. Efremenko, K., Reingold, O.: How well do random walks parallelize? In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol. 5687, pp. 476–489. Springer, Heidelberg (2009)

13. Elsässer, R., Sauerwald, T.: Tight bounds for the cover time of multiple random walks. Theoretical Computer Science 412(24), 2623–2641 (2011)

14. Gasieniec, L., Klasing, R., Martin, R.A., Navarra, A., Zhang, X.: Fast periodic graph exploration with constant memory. Journal of Computer and System Sciences 74(5), 808–822 (2008)

15. Gąsieniec, L., Radzik, T.: Memory efficient anonymous graph exploration. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 14–29. Springer, Heidelberg (2008)

16. Ikeda, S., Kubo, I., Yamashita, M.: The hitting and cover times of random walks on finite graphs using local degree information. Theoretical Computer Science 410(1), 94–100 (2009)

17. Kijima, S., Koga, K., Makino, K.: Deterministic random walks on finite graphs. In: ANALCO, pp. 18–27 (2012)

18. Klasing, R., Kosowski, A., Pajak, D., Sauerwald, T.: The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks. In: PODC, pp. 365–374 (2013)

19. Kosowski, A.: A $\tilde{o}(n^2)$ time-space trade-off for undirected $s-t$ connectivity. In: SODA, pp. 1873–1883 (2013)
20. Kosowski, A., Navarra, A.: Graph decomposition for memoryless periodic exploration. Algorithmica 63(1-2), 26–38 (2012)

21. Lovász, L.: Random walks on graphs: A survey. Bolyai Society Mathematical Studies 2, 353–397 (1996)

22. Malpani, N., Chen, Y., Vaidya, N.H., Welch, J.L.: Distributed token circulation in mobile ad hoc networks. IEEE Transactions on Mobile Computing 4(2), 154–165 (2005)

23. Nonaka, Y., Ono, H., Sadakane, K., Yamashita, M.: The hitting and cover times of metropolis walks. Theoretical Computer Science 411(16-18), 1889–1894 (2010)

24. Priezzhev, V., Dhar, D., Dhar, A., Krishnamurthy, S.: Eulerian walkers as a model of self-organized criticality. Physical Review Letters 77(25), 5079–5082 (1996)

25. Sauerwald, T.: Expansion and the cover time of parallel random walks. In: PODC, pp. 315–324. ACM (2010)

26. Wagner, I.A., Lindenbaum, M., Bruckstein, A.M.: Distributed covering by ant-robots using evaporating traces. IEEE Transactions on Robotics and Automation 15(5), 918–933 (1999)

27. Yanovski, V., Wagner, I.A., Bruckstein, A.M.: A distributed ant algorithm for efficiently patrolling a network. Algorithmica 37(3), 165–186 (2003)