On r-Simple k-Path and Related Problems Parameterized by k/r

Gregory Z. Gutin, Magnus Wahlström, Meirav Zehavi

Abstract

This paper investigates the computational complexity of graph and set problems under relaxed disjointness constraints. Specifically, it examines the $r$-Simple $k$-Path problem and its variants, where vertices or elements can be repeated up to $r$ times. The authors show that many of these problems are Fixed-Parameter Tractable (FPT) when parameterized by the ratio $k/r$, providing new algorithmic upper bounds and identifying hard cases like monomial detection.

Introduction

In classical graph theory, the $k$-Path problem—finding a simple path of length $k$—is a well-known NP-hard problem. A natural generalization is the $r$-Simple $k$-Path problem, where the constraint of vertex uniqueness is relaxed to allow up to $r$ visits per vertex. While previous algorithms for this problem existed, they typically suffered from a dependency on $\log r$ in the exponent. Given that $r$ can be arbitrarily large, this dependency represents a significant computational bottleneck.

The authors propose parameterizing these problems by the ratio $k/r$. This approach reflects the intuition that as the allowed repetitions $r$ increase relative to the total length $k$, the problem should become easier.

Algorithmic Frameworks

The paper employs distinct strategies for different graph types and problem variants:

Directed and Undirected Graphs

For directed graphs, the authors utilize Color Coding combined with "enriched topologies"—small structural templates of potential walks. These templates are embedded into the graph using Integer Linear Programming (ILP) and dynamic programming, resulting in an FPT algorithm with a running time of $2^{O((k/r)^2 \log(k/r))} \cdot poly(n)$.

In the undirected case, the problem admits a more efficient "single-exponential" algorithm ($2^{O(k/r)} \cdot poly(n)$). The authors show that any solution can be decomposed into a sparse Eulerian multigraph and a subgraph with treewidth at most 2. For instances with very large $r$, they leverage flow networks and the observation that the graph must have a bounded vertex cover number to avoid a solution.

Set and Multiset Packing

The authors also investigate the $p$-Set $(r, q)$-Packing problem, which asks for a subcollection of $q$ sets of size $p$ such that each element appears at most $r$ times.

Definition of the p-Set (r,q)-Packing problem.

Using the method of Representative Sets, they prove this problem is FPT and provide a polynomial kernel when $p$ is constant. However, they find that the multiset version of the problem is significantly more difficult.

Definition of the p-Multiset (r,q)-Packing problem.

Complexity Landscape and Key Results

The research highlights a sharp divide between different problem classes:

  • Graph Paths: Both directed and undirected $r$-simple $k$-path problems are FPT under the $k/r$ parameterization.
  • Monomial Detection: Contrary to the graph versions, $(r, k)$-Monomial Detection is shown to be para-NP-hard. This indicates that the algebraic version does not share the same tractability as the path version when parameterized by $k/r$.
  • Multiset Packing: The $p$-Multiset Packing problem is proven to be $W[1]$-hard, marking another boundary of tractability.

Conclusion and Future Work

The paper successfully establishes $k/r$ as a robust parameter for understanding relaxed packing and path problems. Key open questions remain, particularly regarding the gap between directed and undirected path algorithms. Future research may seek a single-exponential algorithm for the directed case or further characterize the boundaries of tractability for monomial detection in various algebraic structures.

Summary updated

BibTeX
@inproceedings{gutin2019r,
  author = {Gregory Z. Gutin and Magnus Wahlström and Meirav Zehavi},
  title = {{On r-Simple k-Path and Related Problems Parameterized by k/r}},
  booktitle = {SODA},
  year = {2019},
  doi = {10.1137/1.9781611975482.105},
}
Figure