Collective Graph Exploration Parameterized by Vertex Cover

Siddharth Gupta, Guy Sa'ar, Meirav Zehavi

TL;DR

This paper explores the parameterized complexity of the Collective Graph Exploration (CGE) problem in the offline setting, where $k$ robots must traverse every edge of a graph within an energy budget $B$. The authors prove that the problem is W[1]-hard with respect to the number of robots $k$ even on trees of treedepth 3, but becomes fixed-parameter tractable (FPT) when parameterized by the graph's vertex cover number ($\text{vc}$). Additionally, they develop an efficient greedy approximation algorithm that solves the exploration time minimization problem within an additive error of $8 \cdot \text{vc}(G)$.

What Problem Does This Paper Address?

In Collective Graph Exploration (CGE), a team of $k$ robots starts at a designated root vertex $r$ in an undirected graph $G$. The goal is to determine if the robots can collaboratively traverse every edge in $G$ and return to $r$ such that no single robot travels more than budget $B$ steps (edges).

While CGE has been heavily investigated in online settings (where the graph is unknown and discovered on the fly), its offline complexity remained largely open for general graphs. The problem is notoriously difficult: it is NP-hard even on unweighted trees. A natural question in parameterized complexity is whether structural parameters (like treewidth or treedepth) can make the problem tractable. This paper settles the computational boundary:

  • Is CGE tractable when parameterized by the number of robots $k$ or treedepth?
  • Can we find exact or near-optimal solutions efficiently when graphs have small vertex cover numbers (a common structure in hub-and-spoke delivery or urban road networks)?

Methods

The paper's technical framework relies on several core innovations:

  1. Eulerian Cycle Reinterpretation: Instead of searching directly for $k$ walks, the authors reframe the problem as partitioning/covering the edge set into $k$ multisets $\hat{E}_1, \dots, \hat{E}_k$ such that each multiset induces a connected graph containing $r$, every vertex in the induced subgraph has an even degree (Eulerian condition), and $\max_i |\hat{E}_i| \le B$.

  2. FPT Algorithm via Integer Linear Programming (ILP):

  3. Skeletons and Valid Pairs: Any Eulerian multigraph per robot is decomposed into a small connected "skeleton" subgraph covering root $r$ and parts of the vertex cover ($\text{VC}$), plus a collection of small cycles (length $\le 2|\text{VC}|$).
  4. Cycle Normalization: The authors observe that almost all cycles can be reduced to simple 4-cycles; the number of non-4-cycles is strictly bounded by a function of $|\text{VC}|$.
  5. Type Abstraction: Vertices in the independent set $V \setminus \text{VC}$ are grouped into equivalence classes based on their neighborhoods. The algorithm defines vertex types, robot types, and cycle types.
  6. By bounding the number of types by $f(\text{vc})$, the problem is expressed as an ILP feasibility instance with $t = f(\text{vc})$ variables, which is solvable in FPT time using Lenstra–Kannan algorithms.
  7. Additive Approximation Algorithm: A greedy strategy balances robot workloads. It first ensures all independent set vertices have even degree by duplicating edges locally, distributes edges incident to the independent set among robots in a round-robin schedule, and then connects each robot's graph using a spanning tree of the vertex cover $G[\text{VC}]$, patching vertex parities within $\text{VC}$.

  8. W[1]-Hardness Reduction: The authors establish hardness by reducing from Unary Exact Bin Packing (which they prove is W[1]-hard parameterized by the number of bins $k$) to CGE on star-like trees of treedepth 3.

Datasets

Not discussed in the paper. (The paper is purely theoretical; no empirical benchmark datasets were used or introduced.)

Key Insights and Ideas

  • Hardness at Very Low Treedepth: Bounding treedepth to just 3 does not tame the problem—it remains W[1]-hard parameterized by $k$. This formally rules out FPT algorithms parameterized by $k + \text{treedepth}$ (unless $\text{FPT} = \text{W}[1]$) and justifies looking at the vertex cover number.
  • Eulerian Cycle Parity Decoupling: By transforming walk construction into edge-multiset Eulerian subgraphs, connectivity issues are isolated to the vertex cover, while parity constraints on independent set vertices can be satisfied independently.
  • Near-Optimal Parity Patching: Independent set vertices only ever need edge traversals in pairs (to maintain even parity). Thus, the only "wasted" budget comes from traversing and re-balancing edges inside the vertex cover, yielding an additive error that depends solely on $\text{vc}(G)$ rather than $|V(G)|$ or $|E(G)|$.

Key Results

  • FPT Classification: CGE is fixed-parameter tractable parameterized by the vertex cover number $\text{vc}(G)$.
  • Fast Additive Approximation: There exists a deterministic algorithm running in $O((|V(G)| + |E(G)|) \cdot k)$ time that computes an exploration strategy with an additive approximation factor of at most $8 \cdot \text{vc}(G)$ above the optimal budget $B^*$.
  • Intractability Boundary: CGE is W[1]-hard parameterized by the number of robots $k$, even when restricted to trees with treedepth $\le 3$.

Limitations and Future Work

  • Large ILP Constants: The FPT algorithm relies on Lenstra's algorithm for ILP with a variable count that is exponential/superpolynomial in $\text{vc}(G)$, making the exact FPT algorithm primarily of theoretical interest rather than practical implementation.
  • Gap Between Treedepth and Vertex Cover: While treedepth 3 is W[1]-hard and vertex cover is FPT, other structural graph parameters situated between treedepth and vertex cover (such as feedback vertex set or twin cover) remain unexplored for offline CGE.
  • Edge Weights: The hardness holds for unweighted graphs; extending the additive approximation guarantees to general edge-weighted settings is an open challenge.

Summary updated

Abstract

We initiate the study of the parameterized complexity of the Collective Graph Exploration (CGE) problem. In CGE, the input consists of an undirected connected graph G and a collection of k robots, initially placed at the same vertex r of G, and each one of them has an energy budget of B. The objective is to decide whether G can be explored by the k robots in B time steps, i.e., there exist k closed walks in G, one corresponding to each robot, such that every edge is covered by at least one walk, every walk starts and ends at the vertex r, and the maximum length of any walk is at most B. Unfortunately, this problem is NP-hard even on trees [Fraigniaud et al., 2006]. Further, we prove that the problem remains W[1]-hard parameterized by k even for trees of treedepth 3. Due to the para-NP-hardness of the problem parameterized by treedepth, and motivated by real-world scenarios, we study the parameterized complexity of the problem parameterized by the vertex cover number (vc) of the graph, and prove that the problem is fixed-parameter tractable (FPT) parameterized by vc. Additionally, we study the optimization version of CGE, where we want to optimize B, and design an approximation algorithm with an additive approximation factor of O(vc).
BibTeX
@inproceedings{gupta2023collective,
  author = {Siddharth Gupta and Guy Sa'ar and Meirav Zehavi},
  title = {{Collective Graph Exploration Parameterized by Vertex Cover}},
  booktitle = {IPEC},
  year = {2023},
  url = {https://openreview.net/forum?id=bJ1Ijh3zOV},
}

Loading related content...

Figure