Map construction
Agents must not only visit every node but output a map of the anonymous graph, up to isomorphism.
Problem statement and measuresexpand
Agents explore an unknown anonymous port-labelled graph and must output a map: a port-labelled graph, kept in the agent's memory, that is isomorphic to the explored graph (with the ports), with the agent's current node indicated. Time is the number of moves.
Measures: Cost, moves until the map is built.
One agent, no marking
standard settingverifiedKnowing upper bounds on \(n\) and on the degree, one agent builds the quotient graph of an anonymous graph without marking anything, by following a universal exploration sequence.
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.
- Timing: asynchronous
- Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
- Agents: one agent
- A single agent.
- Knowledge: bound on \(n\)
- An upper bound \(N\ge n\) is known.
- Markers: no markers
- No markers.
- Whiteboards: no whiteboards
- No whiteboards.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
Statement for this variant
The agent knows an upper bound \(N\ge n\) (and a bound on the maximum degree; \(N-1\) will do) and may not mark nodes. Following Chalopin et al. 2010, it must output the quotient graph of \(G\) with its port numbering, the multigraph obtained by merging nodes with the same view; this is \(G\) itself exactly when all nodes have distinct views, and nothing more can be learned, since graphs with the same quotient graph are indistinguishable to the agent. Time is the number of edge traversals; local computation is free.
What is known
Results, in order of publication
Introductory and current best (Proposition 6): follow a universal exploration sequence \(U(2N^2,\Delta)\) of length \(O(N^6\Delta^2\log N)\) from Aleliunas et al., record the signature, and compute the smallest graph with that signature; memory of the same order. The paper writes \(n\) and \(d\) for the known bounds. Using the routines of Czyzowicz, Kosowski and Pelc Czyzowicz et al. 2012 gives \(O(n^{10}\Delta^5\log^2 n)\) time with \(O(n^9\Delta^4\log^2 n)\) memory (as computed in Chalopin et al. 2010).
Proposition 7 (class refinement, as in automaton minimisation): slightly more time for much less memory.
Proposition 9: breadth-first construction that recognises a node by walking its path back to the marked home base; the output is an exact copy of \(G\). With a marked start and no knowledge, Proposition 8 also computes a polynomial bound \(N\ge n\) with \(\Theta(\log n)\) bits, so map construction is possible in polynomial time with optimal memory.
Open questions
None recorded for this variant.
Notes
Checked against the full text of Chalopin et al. 2010. Which bound needs what: without any marked node the agent must know bounds on \(n\) and on the degree (Propositions 6 and 7, \(O(N^6\Delta^2\log N)\) and \(O(N^6\Delta^3\log N)\)); with a marked starting node no knowledge is needed (Propositions 8 and 9, \(O(n^3\Delta)\) moves and \(O(n\Delta\log n)\) bits). The paper writes that "it is not possible to perform exploration with stop in unlabelled graphs of arbitrary size and topology" without a marked node; a marked home base is "a much weaker assumption compared to allowing the agent to have a pebble". The same paper solves rendezvous of two agents with marked home bases, even asynchronously, in \(O(n^4\Delta^2)\) moves per agent whenever it is deterministically possible, and detects when it is not (Propositions 10 and 11). The timing axis is not set because a single agent's moves are counted regardless of timing. Das 2019 summarises that a full map is obtainable only for covering-minimal graphs; in the paper's terms, an exact copy is obtained exactly when all views are distinct. The \(O(n^3\Delta)\) bound is the one Disser, Hackfeld and Klimm report Disser et al. 2019.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.