Tight bounds for undirected graph exploration with pebbles and multiple agents

DOI10.1145/3356883zbMATH Open1473.68119arXiv1805.03476OpenAlexW2980598507MaRDI QIDQ5215469FDOQ5215469

Max Klimm, Jan Hackfeld, Y. Disser

Publication date: 11 February 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We study the problem of deterministically exploring an undirected and initially unknown graph with $n$ vertices either by a single agent equipped with a set of pebbles, or by a set of collaborating agents. The vertices of the graph are unlabeled and cannot be distinguished by the agents, but the edges incident to a vertex have locally distinct labels. The graph is explored when all vertices have been visited by at least one agent. In this setting, it is known that for a single agent without pebbles $Theta(logn)$ bits of memory are necessary and sufficient to explore any graph with at most $n$ vertices. We are interested in how the memory requirement decreases as the agent may mark vertices by dropping and retrieving distinguishable pebbles, or when multiple agents jointly explore the graph. We give tight results for both questions showing that for a single agent with constant memory $Theta(loglogn)$ pebbles are necessary and sufficient for exploration. We further prove that the same bound holds for the number of collaborating agents needed for exploration. For the upper bound, we devise an algorithm for a single agent with constant memory that explores any $n$-vertex graph using $mathcalO(loglogn)$ pebbles, even when $n$ is unknown. The algorithm terminates after polynomial time and returns to the starting vertex. Since an additional agent is at least as powerful as a pebble, this implies that $mathcalO(loglogn)$ agents with constant memory can explore any $n$-vertex graph. For the lower bound, we show that the number of agents needed for exploring any graph of size $n$ is already $Omega(loglogn)$ when we allow each agent to have at most $mathcalO(log{n}^{1-varepsilon})$ bits of memory for any $varepsilon>0$. This also implies that a single agent with sublogarithmic memory needs $Theta(loglogn)$ pebbles to explore any $n$-vertex graph.

Full work available at URL: https://arxiv.org/abs/1805.03476

Recommendations

• Undirected Graph Exploration with ⊝(log log n) Pebbles
• Structural Information and Communication Complexity
• Using a collective of agents for exploration of undirected graphs
• scientific article; zbMATH DE number 1775412
• Fast collaborative graph exploration

zbMATH Keywords

multi-agent systemgraph explorationspace efficiencypebbles

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Agent technology and artificial intelligence (68T42) Distributed algorithms (68W15)

Cited In (16)

• An improved lower bound for competitive graph exploration
• State complexity of transforming graph-walking automata to halting, returning and reversible
• Zero-memory graph exploration with unknown inports
• Pebble guided near optimal treasure hunt in anonymous graphs
• Lower Bounds for Graph Exploration Using Local Policies
• Graph exploration by a deterministic memoryless automaton with pebbles
• Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles
• Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs
• Homomorphisms and inverse homomorphisms on graph-walking automata
• Undirected Graph Exploration with ⊝(log log n) Pebbles
• A time to cast away stones
• Homomorphisms on graph-walking automata
• Exploration of dynamic networks: tight bounds on the number of agents
• Pebble guided optimal treasure hunt in anonymous graphs
• Exploration of a finite graph by a collective of agents
• State complexity of union and intersection on graph-walking automata

This page was built for publication: Tight bounds for undirected graph exploration with pebbles and multiple agents

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215469)