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

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

This paper, titled "r-Simple k-Path and Related Problems Parameterized by k/r," explores the computational complexity of graph and set problems where the usual constraints of "disjointness" are relaxed. Instead of asking for a path where every vertex is unique, what if we allow each vertex to be visited up to $r$ times? The authors demonstrate that for many of these problems, the difficulty depends not on the total size of the solution ($k$), but on the ratio of the size to the allowed repetitions ($k/r$).

TL;DR

The authors prove that finding an "$r$-simple" path of length $k$ (where each vertex is visited $\le r$ times) is Fixed-Parameter Tractable (FPT) when parameterized by the ratio $k/r$. They provide a single-exponential algorithm for undirected graphs and resolve open questions regarding set packing and monomial detection in this "relaxed" setting.

What Problem Does This Paper Address?

In classical graph theory, the $k$-Path problem asks if a graph contains a simple path of length $k$. This is a famous NP-hard problem. A natural relaxation is the $r$-Simple $k$-Path: find a walk of total length $k$ where no single vertex appears more than $r$ times.

Previous research established that this problem is solvable, but the algorithms often included a $\log r$ factor in the exponent of their running time. Since $r$ can be much larger than the number of vertices in the graph, this factor is a significant bottleneck. The authors set out to determine if these problems are Fixed-Parameter Tractable (FPT) using only the ratio $k/r$ as the parameter, effectively removing the dependency on the magnitude of $r$ itself.

Methods

The authors employ a variety of sophisticated algorithmic techniques tailored to different versions of the problem:

  • For Directed Graphs: They use a "chain of reductions" and a technique called Color Coding. They introduce the concept of "enriched topologies"—small templates of how a walk might look—and use Integer Linear Programming (ILP) and dynamic programming to check if these templates can be "embedded" into the larger graph.
  • For Undirected Graphs: The approach is more structural. They show that any solution can be decomposed into two parts: a sparse "Eulerian" multigraph and a graph with very low treewidth (specifically, treewidth 2). For cases where $r$ is very large, they prove the graph's vertex cover number becomes bounded, allowing them to solve the problem using Flow Networks.
  • For Set Packing: They utilize Representative Sets, a powerful tool in parameterized complexity that allows one to prune a large collection of sets down to a small "representative" subset that preserves the existence of a solution.
  • For Monomial Detection: They use a reduction from the Partition Problem to prove hardness.

Datasets

This is a theoretical computer science paper focused on algorithm design and complexity analysis. No empirical datasets or benchmarks were used for evaluation.

Key Insights and Ideas

  • The Power of the Ratio: The core "aha moment" is that the complexity of these relaxed problems is governed by $k/r$. If you allow more repetitions ($r$), the problem actually becomes easier to solve relative to the total length ($k$).
  • Undirected vs. Directed: The paper reveals a sharp divide in complexity. While both are FPT, the undirected case is significantly more efficient (single-exponential $2^{O(k/r)}$) than the directed case ($2^{O((k/r)^2 \log(k/r))}$).
  • Monomial Detection is Harder: Surprisingly, while $r$-simple paths and monomial detection are often linked, the authors prove that (r, k)-Monomial Detection is para-NP-hard. This means it's unlikely to be FPT when parameterized by $k/r$ alone, marking a fundamental difference between the graph and algebraic versions of the problem.
  • Bounded Structural Complexity: In the undirected case, if $r$ is large enough, the graph must have a small vertex cover to not have a solution, which provides a shortcut for the algorithm.

Key Results

  • Directed $r$-Simple $k$-Path: Solvable in $2^{O((k/r)^2 \log(k/r))} \cdot poly(n)$.
  • Undirected $r$-Simple $k$-Path: Solvable in $2^{O(k/r)} \cdot poly(n)$. This is a "single-exponential" result, which is considered optimal for many such problems under the Exponential Time Hypothesis (ETH).
  • $p$-Set $(r, q)$-Packing: Confirmed to be FPT. The authors also provide a polynomial kernel for this problem when $p$ is constant, meaning the problem can be reduced to a core instance whose size doesn't depend on $n$.
  • Hardness: Proved that $p$-Multiset Packing and Monomial Detection are $W[1]$-hard or para-NP-hard in this parameterization.

Limitations and Future Work

  • The Directed Gap: There is still a gap between the directed and undirected running times. A major open question is whether the directed $r$-simple $k$-path can also be solved in single-exponential time ($2^{O(k/r)}$).
  • Generalizing Monomial Detection: The authors suggest further work to characterize exactly which types of polynomials allow for efficient Monomial Detection in this setting.
  • Other Problems: The "relaxed disjointness" framework could be applied to other classic problems, such as finding spanning trees with degree constraints.

Summary updated

Abstract

Abasi et al. (2014) and Gabizon et al. (2015) studied the following problems. In the $r$-Simple $k$-Path problem, given a digraph $G$ on $n$ vertices and integers $r,k$, decide whether $G$ has an $r$-simple $k$-path, which is a walk where every vertex occurs at most $r$ times and the total number of vertex occurrences is $k$. In the $(r,k)$-Monomial Detection problem, given an arithmetic circuit that encodes some polynomial $P$ on $n$ variables and integers $k,r$, decide whether $P$ has a monomial of degree $k$ where the degree of each variable is at most~$r$. In the $p$-Set $(r,q)$-Packing problem, given a universe $V$, positive integers $p,q,r$, and a collection $\cal H$ of sets of size $p$ whose elements belong to $V$, decide whether there exists a subcollection ${\cal H}'$ of $\cal H$ of size $q$ where each element occurs in at most $r$ sets of ${\cal H}'$. Abasi et al. and Gabizon et al. proved that the three problems are single-exponentially fixed-parameter tractable (FPT) when parameterized by $(k/r)\log r$, where $k=pq$ for $p$-Set $(r,q)$-Packing and asked whether the $\log r$ factor in the exponent can be avoided. We consider their question from a wider perspective: are the above problems FPT when parameterized by $k/r$ only? We resolve the wider question by (a) obtaining a $2^{O((k/r)^2\log(k/r))} (n+\log k)^{O(1)}$-time algorithm for $r$-Simple $k$-Path on digraphs and a $2^{O(k/r)} (n+\log k)^{O(1)}$-time algorithm for $r$-Simple $k$-Path on undirected graphs (i.e., for undirected graphs we answer the original question in affirmative), (b) showing that $p$-Set $(r,q)$-Packing is FPT, and (c) proving that $(r,k)$-Monomial Detection is para-NP-hard. For $p$-Set $(r,q)$-Packing, we obtain a polynomial kernel for any fixed $p$, which resolves a question posed by Gabizon et al. regarding the existence of polynomial kernels for problems with relaxed disjointness constraints.
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