Graph Traversal via Connected Mobile Agents
Saswata Jana, Giuseppe F. Italiano, Partha Sarathi Mandal · 2025
Read Graph Traversal via Connected Mobile Agents by Saswata Jana, Giuseppe F. Italiano, Partha Sarathi Mandal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-18683.txt.
Introduction
Saswata Jana and co-authors studied in 2025 how a team of connected agents can walk a whole graph. In their problem, k agents stand on distinct vertices that always form a connected shape. At each step an agent may stay put or move to a neighbor. Together they must produce a spanning walk in as few steps as possible, generalizing the classic Hamiltonian walk problem.
The problem is NP-hard, so the authors design approximation algorithms. For two agents on any graph they give an algorithm within a factor of about three of optimal. For trees they solve a restricted version exactly for any number of agents. They also extend the problem to hypergraphs with a logarithmic-factor algorithm. The work opens a new corner of multi-agent coordination theory.
Catalog record
| CREATOR | Saswata Jana, Giuseppe F. Italiano, Partha Sarathi Mandal |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-18683
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph Traversal via Connected Mobile Agents Saswata Jana, Giuseppe F. Italiano, Partha Sarathi Mandal Abstract This paper considers the Hamiltonian walk problem in the multi-agent coordination framework, referred to as k k -agents Hamiltonian walk problem ( k k -HWP). In this problem, a set of k k connected agents collectively compute a spanning walk of a given undirected graph in the minimum steps. At each step, the agents are at k k distinct vertices and the induced subgraph made by the occupied vertices remains connected. In the next consecutive steps, each agent may remain stationary or move to one of its neighbours. To the best of our knowledge, this problem has not been previously explored in the context of multi-agent systems with connectivity. As a generalization of the well-known Hamiltonian walk problem (when k = 1 k=1 ), k k -HWP is NP-hard. We propose a ( 3 − 1 21 ) (3-\frac{1}{21}) -approximation algorithm for 2-HWP on arbitrary graphs. For the tree, we define a restricted version of the problem and present an optimal algorithm for arbitrary values of k k . Finally, we formalize the problem for k k -uniform hypergraphs and present a 2 ( 1 + ln k ) 2(1+\ln k) -approximation algorithm. This result is also adapted to design an approximation algorithm for k k -HWP on general graphs when k = O ( 1 ) k=O(1) . 1 Introduction Graph traversal is a fundamental problem in computer science and robotics, where the goal is to visit every node of a graph at least once. A key objective of graph traversal is to minimize the number of steps needed to traverse the entire graph. Typically, such tasks can be accomplished by a single agent. However, relying on a single agent can be inefficient, prone to failure, and unsuitable for large or complex environments. These limitations motivate the need for multi-agent systems, where the agents coordinate among themselves to traverse the whole graph while reducing the traversal time and handling failures effectively. One major challenge in coordinating multiple agents is ensuring safe and reliable communication during the traversal. In many practical systems, such as swarm robotics or drone networks, connectivity among agents is essential to maintain real-time coordination, prevent collisions, and quickly react to unexpected failures. In addition, the connectivity constraint also plays a key role in fault-tolerant settings. For instance, if one agent fails, the connected agents can detect the failure and either compensate for the loss or design a strategy to recover the lost functionality. Preliminaries, Related works and Problem definition: Let G=(V,E) be a simple undirected connected graph (without self-loops and multiple edges), where V is the set of vertices and E is the set of edges. An edge between two vertices v_{i} and v_{j} is denoted by (v_{i},v_{j}) . Let n=|V| be the number of vertices and m=|E| be the number of edges of G . N(v) is the open neighbourhood of the vertex v\in V , consisting of all its neighbours, while N[v] is the closed neighbourhood of v , defined as N[v]=N(v)\cup\{v\} . A sequence of distinct vertices P=\{v_{1},v_{2},\cdots,v_{p}\} is called a path of the graph G if (v_{i},v_{i+1})\in E~\forall i\in\{1,2,\cdots,p-1\} . Whenever both endpoints of a path v_{1} and v_{p} are explicitly mentioned, we denote the path as P_{v_{1}v_{p}} . Additionally, if v_{1}=v_{p} , the sequence is called a cycle of the graph G . If G admits a path of length (n-1) , then the path is called a Hamiltonian path . Similarly, if a graph has a cycle of length n , then the cycle is called a Hamiltonian cycle , and the graph is called Hamiltonian graph . In other words, a graph is called Hamiltonian if there exists a cycle that passes through each vertex of G exactly once. The problem of finding a Hamiltonian cycle in a graph, or checking whether a given graph is Hamiltonian, is known as the Hamiltonian cycle problem , which is one of Karp’s 21 NP-complete problems [ 13 ] . Given that a class of graphs lacks a Hamiltonian path or cycle, there is growing interest in determining a minimum-length spanning walk of those graphs. A walk is a path with some possible repeated vertices. If both endpoints of the walk are the same (or different), the walk is termed a closed (or open) walk. A walk is a spanning walk of G if it passes through each vertex of G at least once. A closed spanning walk of minimum length is termed as Hamiltonian walk . The length of a Hamiltonian walk of the graph G is known as Hamiltonian number and denoted as h^{+}(G) . If h^{+}(G)=n , the graph G is Hamiltonian and vice versa. n\leq h^{+}(G)\leq 2(n-1) . It is well known that h^{+}(G)=2n-2 iff G is a tree [ 9 ] . An open spanning walk of G is a spanning walk with different endpoints, and we use the notation h^{-}(G) to denote the length of the minimum open spanning walk of G . Finding the minimum-length open spanning walk of a graph is known as the open Hamiltonian walk problem . If the graph G is Hamiltonian, then h^{-}(G)=(n-1) . However, the converse is not true. The challenge of finding an open spanning walk is closely related to the classic traveling salesman problem (TSP), in which the objective is to locate a minimum weight Hamiltonian cycle in a given complete weighted graph. Christofides-Serdyukov [ 5 ] [ 16 ] proposed a \frac{3}{2} -approximation algorithm for TSP if the weight function satisfies the triangular inequality. After decades, Karlin et al. [ 12 ] give a randomized \frac{3}{2}-\epsilon approximation algorithm for some \epsilon>10^{-36} . A polynomial time approximation scheme (PTAS) exists for some special instances of the TSP, such as for Euclidean TSP [ 2 ] , [ 15 ] , planar TSP [ 1 ] , [ 10 ] , [ 14 ] , and bounded genus TSP [ 6 ] . The multiple traveling salesman problem [ 4 ] is a generalization of the TSP, where multiple salesmen independently (no restriction to the connectivity) visit the vertices of the graph. Hoogeveen [ 11 ] modified Christofide’s heuristic to find a minimum weight Hamiltonian path of a given weighted complete graph when the weights satisfy the triangular inequality. The modified heuristic also gives a \frac{3}{2} approximation factor, which is still the best-known factor for the problem. We can apply the modified Christofides heuristic to find an open spanning walk for an undirected, unweighted, and connected graph G by converting it into a complete weighted graph. To do this, we assign a weight equal to one to each existing edge and add all missing edges with a weight equal to the length of the shortest paths between corresponding vertices. We address the open Hamiltonian walk problem from the perspective of a mobile agent that explores the entire graph G in a minimum number of steps, starting from an arbitrary vertex. At each step, the agent can move to one of its neighbouring vertices. Therefore, any minimum open-spanning walk constitutes a feasible solution. Additionally, we can apply the modified Christofide’s heuristic