Deciding a Graph Property by a Single Mobile Agent: One-Bit Memory Suffices
share
We investigate the computational power of the deterministic single-agent model where the agent and each node are equipped with a limited amount of persistent memory. Tasks are formalized as decision problems on properties of input graphs, i.e., the task is defined as a subset 𝒯 of all possible input graphs, and the agent must decide if the network belongs to 𝒯 or not. We focus on the class of the decision problems which are solvable in a polynomial number of movements, and polynomial-time local computation. The contribution of this paper is the computational power of the very weak system with one-bit agent memory and O(1)-bit storage (i.e. node memory) is equivalent to the one with O(n)-bit agent memory and O(1)-bit storage. We also show that the one-bit agent memory is crucial to lead this equivalence: There exists a decision task which can be solved by the one-bit memory agent but cannot be solved by the zero-bit memory (i.e., oblivious) agent. Our result is deduced by the algorithm of simulating the O(n)-bit memory agent by the one-bit memory agent with polynomial-time overhead, which is developed by two novel technical tools. The first one is a dynamic s-t path maintenance mechanism which uses only O(1)-bit storage per node. The second one is a new lexicographically-ordered DFS algorithm for the mobile agent system with O(1)-bit memory and O(1)-bit storage per node. These tools are of independent interest.
READ FULL TEXT