Deciding graph properties by mobile agents
Agents in an anonymous graph must decide together whether their starting configuration has a property, such as "the graph is a tree": which properties can they decide, with what help, and with how little memory?
Problem statement and measuresexpand
\(k \ge 1\) agents start at nodes of a connected undirected graph \(G\) with \(n\) nodes; the nodes are anonymous, and at each node the edges carry distinct port numbers. Each agent has a distinct identifier and an input string, and several agents may start at the same node. The agents move in synchronous rounds, crossing at most one edge per round, cannot mark nodes unless a setting gives whiteboards, and exchange everything they know when they are at the same node; no agent knows anything else in advance. A configuration is the graph with the agents' start nodes and inputs. A decision problem \(\Pi\) is a set of configurations, closed under automorphisms of \(G\) that preserve ports, whose membership a centralised algorithm that sees the whole configuration can decide. The agents decide \(\Pi\) if every agent eventually outputs yes or no, all agents output yes when the configuration is in \(\Pi\), and at least one outputs no when it is not Fraigniaud & Pelc 2017. In verification every agent also receives a certificate: for every configuration in \(\Pi\) some certificate makes all agents output yes, and for every other configuration no certificate does. The question is which decision problems the agents can decide, in particular whether all of them, and with how much memory. Time is in rounds; memory in bits per agent.
Measures: Time, rounds until every agent has decided; Memory, bits per agent.
One agent with whiteboards and little memory
verifiedOne bit of agent memory, with constant-size whiteboards, decides everything that \(O(n)\) bits decide in polynomial time; zero bits do not.
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.
- Node identifiers: anonymous nodes
- Nodes have no identifiers; an agent at \(v\) sees only \(\deg(v)\) and the port numbers \(1,\dots,\deg(v)\), which are assigned locally and independently at each endpoint of an edge.
- Identifiers: anonymous
- All agents run the same deterministic algorithm on the same input; no agent has a label. Formally the label function is constant: \(\mathrm{id}(a)=\mathrm{id}(b)\) for all agents \(a,b\).
- Communication: no communication
- Agents exchange no messages; an agent at \(v\) observes only the number of agents at \(v\) (and, where stated, whether that number changed).
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Node memory: whiteboards
- Each node \(v\) has a whiteboard of bounded size that agents at \(v\) can read and write, with mutual exclusion.
- Number of agents: one agent
- Exactly one agent, \(k = 1\): configurations with more agents are excluded.
- Certificates: decide
- The agents receive only their identifiers and inputs.
- Knowledge of the graph: no knowledge
- The agents know nothing about \(G\).
Statement for this variant
One agent, no inputs, whiteboards of \(O(1)\) bits that are all \(0\) at the start. A decision problem is a set of graphs; the agent must stop within \(\mathrm{poly}(n)\) moves, with polynomial local computation in each step, and write the answer on the whiteboard of its final node. The question is how much memory the agent needs.
What is known
- the problem whether \(n\) is odd: an agent without memory and with \(O(1)\)-bit whiteboards cannot explore every graph Cohen et al. 2008, so on some graph it decides without visiting a node, and a leaf added there changes the answer (Theorem 2, Lemma 4)
- whiteboards of \(O(1)\) bits
Results, in order of publication
Introductory and current best (Theorem 1): the agent orders the nodes by a depth-first search in port order that needs only \(O(1)\) bits of memory and of whiteboard (Theorem 3), uses the whiteboards along that order as the tape of a Turing machine that simulates the \(O(n)\)-bit agent, and keeps paths between the positions it needs with \(O(1)\) bits per node; \(O(1)\) bits of agent memory are then reduced to one by carrying them across an edge one bit per round trip. The overhead is polynomial.
Open questions
None recorded for this variant.
Notes
Izumi, Kakizawa, Kawabata, Kitamura and Masuzawa call the classes \(\mathsf{PAGT}(g(n), h(n))\): problems decidable in polynomial time with \(g(n)\) bits of agent memory and \(h(n)\) bits per whiteboard Izumi et al. 2022. They name planarity, bipartiteness and bounds on the diameter or the treewidth as examples of decision problems in this sense. Checked against the full text (arXiv v1, a preprint).
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.