FPT Algorithms for Weighted Graphs Can be (Almost) as Efficient as for Unweighted

Hadas Shachnai, Meirav Zehavi

Abstract

We introduce a novel multivariate approach for solving weighted parameterized problems. In our model, given an instance of size $n$ of a minimization (maximization) problem, and a parameter $W \geq 1$, we seek a solution of weight at most (or at least) $W$. We use our general framework to obtain efficient algorithms for such fundamental graph problems as Vertex Cover, 3-Hitting Set, Edge Dominating Set and Max Internal Out-Branching. The best known algorithms for these problems admit running times of the form $c^W n^{O(1)}$, for some constant $c>1$. We improve these running times to $c^s n^{O(1)}$, where $s \leq W$ is the minimum size of a solution of weight at most (at least) $W$. If no such solution exists, $s=\min\{W,m\}$, where $m$ is the maximum size of a solution. Clearly, $s$ can be substantially smaller than $W$. In particular, the running times of our algorithms are (almost) the same as the best known $O^*$ running times for the unweighted variants.

Introduction

Many core problems in graph theory, such as finding the smallest set of vertices that "cover" all edges, are NP-hard. To handle this, researchers use Fixed-Parameter Tractable (FPT) algorithms. In unweighted graphs, these algorithms typically have a running time of $O^*(c^k)$, where $n$ is the input size, $c$ is a constant, and $k$ is the size of the solution. Because $k$ is usually small, these algorithms are very efficient in practice.

However, when weights are added to vertices or edges, the parameter usually becomes the total weight $W$. Since $W$ can be much larger than the number of elements $k$, traditional weighted FPT algorithms with running times like $O^*(c^W)$ become prohibitively slow. This paper addresses a central challenge: Can we design algorithms for weighted graphs that depend on the solution size rather than the total weight?

Methodology

The authors propose a multivariate approach that adds a secondary "size" parameter $k$ to the weight parameter $W$. Their framework relies on several key innovations:

  • Iterative Deepening on Size: The algorithm starts by looking for a solution of size $k=1$ with weight at most $W$. It then iteratively increases $k$ until a solution is found or a maximum possible size is reached.
  • "Flexible" Failures: A critical feature of the framework is that it allows sub-routines to "fail" (return NIL) under specific conditions. Specifically, if a solution of weight $\le W$ and size $\le k$ exists, the algorithm must find some solution of weight $\le W$. If not, it can return NIL. This flexibility allows for more aggressive branching and reduction rules.
  • Weight-Manipulating Reduction Rules: Unlike standard unweighted algorithms, this framework uses rules that actively modify the weights of vertices/edges to simplify the graph while maintaining the "safety" of the search.
  • Bounded Search Trees: The authors adapt the classic search tree technique. While they track the weight $W$ to ensure correctness, they analyze the "branching vectors" relative to the size parameter $k$.

Key Results

The paper provides new upper bounds for several fundamental NP-hard problems, where $s$ is the minimum size of a solution with weight at most (or at least) $W$.

Summary of running times for weighted problems compared to unweighted counterparts.

As shown in the table above, the new algorithms significantly outperform previous state-of-the-art weighted algorithms. Key improvements include:

  • Weighted Vertex Cover (WVC): Improved from $O^*(1.396^W)$ to $O^*(1.381^s)$. Since $s \le W$, this is a massive speedup for graphs with large weights.
  • Weighted 3-Hitting Set (W3HS): Achieved $O^*(2.168^s)$, which is remarkably close to the unweighted record of $O^*(2.076^k)$.
  • Weighted Edge Dominating Set (WEDS): Achieved $O^*(2.315^s)$.
  • Weighted Max Internal Out-Branching (WIOB): The authors provide the first-ever FPT results for the weighted version of this maximization problem, achieving $O^*(6.855^s)$.

Key Insights

  • Size is the Better Parameter: Even in a weighted world, the combinatorial "explosion" is often driven by the number of elements chosen, not their numerical values.
  • The Power of "NIL": By allowing the algorithm to return NIL when no "small" solution exists—even if a "large" one does—the authors can use branching rules that would be considered "unsafe" in a standard weighted algorithm.
  • Bridging the Gap: The paper shows that for many problems, the "base" of the exponential running time ($c$ in $c^k$) can be made nearly identical to the best-known unweighted versions.

Discussion and Future Work

While the paper focuses on worst-case asymptotic complexity, it opens new avenues for applying FPT techniques to weighted problems. Future work includes testing performance on real-world graphs and extending the framework to other problems like Weighted Feedback Vertex Set. Notably, while unweighted Vertex Cover has a small "kernel," Weighted Vertex Cover does not admit a polynomial kernel when parameterized by size, suggesting that some fundamental differences between weighted and unweighted problems still remain.

Summary updated

Abstract

We introduce a novel multivariate approach for solving weighted parameterized problems. In our model, given an instance of size $n$ of a minimization (maximization) problem, and a parameter $W \geq 1$, we seek a solution of weight at most (or at least) $W$. We use our general framework to obtain efficient algorithms for such fundamental graph problems as Vertex Cover, 3-Hitting Set, Edge Dominating Set and Max Internal Out-Branching. The best known algorithms for these problems admit running times of the form $c^W n^{O(1)}$, for some constant $c>1$. We improve these running times to $c^s n^{O(1)}$, where $s\leq W$ is the minimum size of a solution of weight at most (at least) $W$. If no such solution exists, $s=\min\{W,m\}$, where $m$ is the maximum size of a solution. Clearly, $s$ can be substantially smaller than $W$. In particular, the running times of our algorithms are (almost) the same as the best known $O^*$ running times for the unweighted variants. Thus, we solve the weighted versions of * Vertex Cover in $1.381^s n^{O(1)}$ time and $n^{O(1)}$ space. * 3-Hitting Set in $2.168^s n^{O(1)}$ time and $n^{O(1)}$ space. * Edge Dominating Set in $2.315^s n^{O(1)}$ time and $n^{O(1)}$ space. * Max Internal Out-Branching in $6.855^s n^{O(1)}$ time and space. We further show that Weighted Vertex Cover and Weighted Edge Dominating Set admit fast algorithms whose running times are of the form $c^t n^{O(1)}$, where $t \leq s$ is the minimum size of a solution.
BibTeX
@article{shachnai2017fpt,
  author = {Hadas Shachnai and Meirav Zehavi},
  title = {{FPT Algorithms for Weighted Graphs Can be (Almost) as Efficient as for Unweighted}},
  journal = {J. Comput. Syst. Sci.},
  year = {2017},
  url = {https://openreview.net/forum?id=aAblFCqrYU},
}
Figure