Exploration of recolourable graphs
A single agent with little or no memory must visit every node of an anonymous graph whose nodes carry colours it can read and rewrite; how many colours are needed, and how much does it help to recolour, to see neighbours or to have port numbers?
Problem statement and measuresexpand
A single deterministic agent starts at a node \(s\) of a connected, simple, undirected, anonymous graph \(G=(V,E)\) with \(n\) nodes, \(m\) edges, maximum degree \(\Delta\) and diameter \(D\). Every node \(v\) holds a colour \(\psi(v)\) from a palette of \(c\) colours that persists between visits. In each step the agent at \(v\) observes \(\psi(v)\) (and, depending on the setting, \(\deg(v)\), port numbers, the entry port, and the multiset of its neighbours' colours), sets \(\psi(v)\) to a new colour (recolours \(v\)) if the setting allows it, and then moves to a neighbour or stops. In the main model Böckenhauer et al. 2023 there are no port numbers: the agent names a colour and the adversary moves it to any neighbour of that colour; the agent is oblivious (it keeps no memory between steps); all nodes start with the initial colour \(c_0\); and the agent must visit every node, return to \(s\) and stop there, from every start and against every adversary. Other settings fix the colours in advance (label-guided exploration), give port numbers, or ask only for perpetual exploration. Measures: the number of colours \(c\), counting \(c_0\) (the main measure); time, the number of moves (traversals of one edge) until termination (or until every node is visited, for perpetual exploration); and the agent's memory. All known results are for one agent.
Measures: Colours, number \(c\) of node colours, counting the initial colour \(c_0\) (for the rotor-router: per node); Time, moves until the agent stops (perpetual: until every node is visited); Memory, bits of agent memory; 0 for an oblivious agent.
Rotor-router with pointers set by a designer
verifiedIf a designer who knows the graph and its port numbers sets the initial pointers, the rotor-router follows an Euler tour from the first move, so it visits every node and locks in within \(O(m)\) moves.
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.
- Port numbers: ports, no entry port
- The edges at \(v\) carry port numbers \(1,\dots,\deg(v)\), assigned by an adversary independently at each endpoint (\(\mathrm{port}_v\)). The agent chooses the port by which it leaves, but on arrival it is not told the port by which it entered (unknown inport).
- View: own node
- At node \(v\) the agent observes \(\psi(v)\), \(\deg(v)\) and nothing about its neighbours (and, where ports exist, what the port axis grants).
- Agent memory: oblivious
- The agent has no internal state: its action (new colour of \(v\), then a move, stay or stop) is a function of its current observation only. Called zero-memory, memoryless or a 1-state robot.
- Recolouring: recolourable
- At every step the agent at \(v\) may set \(\psi(v)\) to any colour of the palette, including back to \(c_0\), any number of times (the convention of Takahashi et al. 2025 and Hiraoka et al. 2026).
- Initial colouring: designer's colours
- Before the agent starts, a designer who knows \(G\) (and the start node) chooses \(\psi_0\). Used with fixed colours this is label-guided exploration Cohen et al. 2008.
- Knowledge: nothing known
- The algorithm is the same for all graphs: it knows neither \(n\) nor \(\Delta\) nor any other parameter (a uniform algorithm in Böckenhauer et al. 2023).
- Termination requirement: perpetual
- Every node is visited at least once (for the rotor-router: infinitely often); the agent never needs to halt.
- Network: any graph
- A finite, simple, connected, undirected, anonymous graph \(G = (V,E)\) with \(n\) nodes.
Statement for this variant
As in the rotor-router setting, the colour of a node is its pointer and the agent leaves by the pointer and advances it cyclically. The adversary numbers the ports; then a designer who knows the graph, its port numbers and the start node chooses the initial pointer at every node (case \(A()P(f)\) of Bampas et al. 2017). The agent must visit every node (and keeps going).
What is known
Results, in order of publication
Introductory and current best (Section 2.1, cases \(P\)-all and \(A()P(f)\)): the designer chooses pointers that make the walk follow an Euler tour of the arcs from the start, so every edge is traversed in both directions, and every node visited, within \(2m\) moves. The bound is on the lock-in time, which bounds the time to visit every node.
Open questions
How few moves does a rotor-router with designer pointers need to visit every node, as opposed to locking in? In Hamiltonian graphs the pointers can follow a Hamiltonian cycle Bampas et al. 2017.
Notes
Bampas, Gąsieniec, Hanusse, Ilcinkas, Klasing and Kosowski let a player who wants a fast lock-in and an adversary choose the pointers and the port order in either order Bampas et al. 2017. This setting is their case \(A()P(f)\): the ports are fixed first and the player answers with the pointers, which reduces to choosing everything and gives \(O(m)\) (Section 2.1). If instead the player must set the pointers before the adversary orders the ports (case \(P(f)A()\)), lock-in takes \(O(m\min(\log m, D))\) moves, with pointers towards the child of largest Strahler rank in a breadth-first search tree (Theorem 3), and some graphs need \(\Omega(m\min(\log m, D))\) moves before lock-in whatever the pointers (Theorem 4). The catalogue has no setting for that order of choices, so Theorems 3 and 4 are recorded here only; they bound lock-in, not the time to visit every node.
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.