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: a pointer in every node
draftA node's colour is a pointer to one of its ports; an oblivious agent that follows and advances it explores any graph in \(O(mD)\) moves from arbitrary pointers, and no oblivious agent without the entry port is faster in the worst case.
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. 2026 and Hiraoka et al. 2026).
- Initial colouring: arbitrary colours
- The initial colouring \(\psi_0 : V \to \{1,\dots,c\}\) is chosen by the adversary; an algorithm must work from every \(\psi_0\) (as with a rotor-router whose pointers are set arbitrarily).
- 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
Ports are numbered, the entry port is not revealed, the agent sees only its own node. The colour of \(v\) is a pointer \(\pi_v \in \{1,\dots,\deg(v)\}\), initially arbitrary. The agent leaves \(v\) by port \(\pi_v\) and advances \(\pi_v\) cyclically. It must visit every node (and keeps going). So a node of degree \(d\) uses \(d\) colours, \(\lceil\log_2 d\rceil\) bits.
What is known
- an oblivious agent without the entry port needs \(\deg(v)\) distinct inputs at \(v\) to leave by every port (Observation 1.1)
- any oblivious agent without the entry port, even with unbounded node memory (Theorem 2.3)
- uniform initial node memory, so it holds a fortiori from arbitrary colours
- on a path, \((n-1)^2\) moves are needed for a worst-case port numbering (Theorem 2.2), which the rotor-router attains
Results, in order of publication
Introductory and current best, as reported by Menc et al. 2017: from arbitrary pointers the walk settles into an Euler tour within \(O(mD)\) moves (the abstract gives \(2mD\) steps), which is \(\Theta(mD)\) in the worst case Bampas et al. 2009. Not checked against the full text.
Open questions
For which graphs (other than paths) is the rotor-router exactly time-optimal among oblivious agents without the entry port Menc et al. 2017?
Notes
The rotor-router (also Propp machine, Edge Ant Walk) goes back to the Eulerian walkers of Priezzhev, D. Dhar, A. Dhar and Krishnamurthy (as cited by Takahashi et al. 2026) Priezzhev et al. 1996; Yanovski, Wagner and Bruckstein used it for patrolling Yanovski et al. 2003. Bampas et al. show that if the pointers may be chosen and the adversary then numbers the ports, the lock-in time drops to \(O(m\min(\log m, D))\) (abstract) Bampas et al. 2009. It is a recolourable node whose palette grows with the degree: a deterministic recolouring rule fixed in advance. Unverified: the \(O(mD)\) bound, taken from Menc et al. 2017, the abstract of Yanovski et al. 2003 and the slides of Bampas et al. 2009.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.