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.
Label-guided: colours fixed by a designer
verifiedIf a designer colours the nodes with three colours, a finite automaton explores every graph and stops within \(20m\) 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 + entry port
- As for port numbers, and on arrival at \(v\) the agent also reads the port \(\mathrm{port}_v(e)\) of the edge \(e\) by which it entered. This is the standard convention of single-agent exploration.
- 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: finite automaton
- The agent is a deterministic automaton with \(K\) states, \(K\) independent of the graph; its action and next state depend on its state and its observation.
- Recolouring: fixed colours
- The colouring \(\psi : V \to \{1,\dots,c\}\) never changes; the agent reads \(\psi(v)\) (and, with neighbour view, its neighbours' colours) but cannot write.
- 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: stop
- The agent visits every node and then halts, at any node.
- Network: any graph
- A finite, simple, connected, undirected, anonymous graph \(G = (V,E)\) with \(n\) nodes.
What is known
- with one colour the labels carry nothing, and no finite automaton explores all graphs Fraigniaud et al. 2005 (Section 5 of Cohen et al. 2008)
- holds even for bounded-degree graphs
- trivial: any agent must visit all \(n\) nodes (stated for trees in Bojko et al. 2022)
Results, in order of publication
Introductory and current best (Theorem 2.1): at most \(20m\) moves. With 1-bit (two-colour) labels, \(O(\log\Delta)\) bits of memory and \(O(\Delta^{O(1)}m)\) moves (Theorem 3.1).
Open questions
Is there a 1-bit (two-colour) labeling with which a finite automaton explores every graph Cohen et al. 2008?
Notes
This is the setting Node labels chosen by the designer of single-agent exploration, seen from the colour side: the flag is planted by a designer and the agent cannot change it. The designer's colouring by depth mod 3 is the same device that Böckenhauer et al. let the agent build itself. Zhang, Zhang and Tang trade the share of black nodes in 1-bit labelings against memory Zhang et al. 2012. Checked against the full text.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.