Linear-Time FPT Algorithms via Network Flow

Yoichi Iwata, Keigo Oka, Yuichi Yoshida

Abstract

This paper presents the first linear-time Fixed-Parameter Tractable (FPT) algorithms for several classic NP-Hard problems, including Odd Cycle Transversal and Almost 2-SAT. By reducing these problems to a generalized integer programming framework known as Binarized IP2 (BIP2) and utilizing incremental network flow updates during branching, the authors achieve a running time of $O(4^k \cdot n)$. This complexity is truly linear relative to the input size, overcoming the high-degree polynomial bottlenecks common in previous FPT approaches.

Introduction

In computational complexity, NP-Hard problems are typically intractable for large inputs. Parameterized complexity offers a solution: if a problem has a small parameter $k$ (such as the solution size), we can design FPT algorithms with runtimes of $O(f(k)n^d)$. However, many existing FPT algorithms suffer from either astronomical exponential factors $f(k)$ or high-degree polynomials $n^d$ (e.g., $n^{10}$), making them impractical for massive datasets.

This research addresses this gap by seeking algorithms where both $f(k)$ is a single exponential (like $4^k$) and $d=1$. The authors achieve this by parameterizing problems based on the "integrality gap"—the distance between an optimal integer solution and its fractional linear programming (LP) relaxation.

The BIP2 Framework and "Above LP" Parameterization

The core of the authors' approach is the Binarized IP2 (BIP2) framework. This class of integer programs is expressive enough to encompass various fundamental problems, including Vertex Cover, Almost 2-SAT, and Split Vertex Deletion.

The authors demonstrate that any BIP2 instance can be reduced in linear time to a specific problem: Vertex Cover Above LP. In this formulation, the parameter $k$ represents the gap between the optimal integer solution and the LP relaxation. This "Above LP" parameterization is particularly powerful for problems that are "almost" solvable via linear programming.

Algorithmic Innovation: Incremental Network Flow

The algorithmic breakthrough lies in how the LP relaxations are handled. These problems typically admit "half-integral" solutions (variables are 0, 1, or 0.5), which can be computed efficiently using maximum flow algorithms.

The Dual-VC optimization problem, which serves as the foundation for the 'Above LP' parameterization and its connection to network flow.

Traditionally, branching in an FPT algorithm requires recomputing the LP solution from scratch at every node of the search tree, which is computationally expensive. The authors propose treating the LP solution as a state—specifically, a flow in a network. When branching on a variable, they update the existing flow using augmenting paths in linear time rather than restarting the optimization. This incremental update ensures that the cost of re-optimizing after a branch is proportional to the change in the problem, not the total size of the input.

Key Results

The paper proves that BIP2 "Above LP" can be solved in $O(4^k(n+m))$ time, where $n$ is the number of variables and $m$ is the number of constraints. This leads to several significant milestones:

  • First Linear-Time FPT Algorithms: The work provides the first linear-time FPT algorithms for Odd Cycle Transversal (minimum vertices to remove to make a graph bipartite) and Almost 2-SAT (minimum clauses to remove for satisfiability).
  • Improved Constants: The exponential factor $4^k$ is significantly more efficient than previous algorithms that relied on larger bases or more complex parameters.
  • Generality: By solving the BIP2 framework, the authors provide a unified solution for a suite of combinatorial optimization problems.

Limitations and Future Work

While $4^k$ is efficient for small $k$, the exponential nature of the runtime remains a barrier for parameters $k > 20$. Additionally, while the most efficient results are demonstrated for "Binary BIP2," the practical performance for non-binary variables may vary. Future research may extend these incremental network flow techniques to broader classes of problems beyond the BIP2 framework, potentially enabling linear-time FPT solutions in other domains of optimization.

Summary updated

Abstract

In the area of parameterized complexity, to cope with NP-Hard problems, we introduce a parameter k besides the input size n, and we aim to design algorithms (called FPT algorithms) that run in O(f(k)n^d) time for some function f(k) and constant d. Though FPT algorithms have been successfully designed for many problems, typically they are not sufficiently fast because of huge f(k) and d. In this paper, we give FPT algorithms with small f(k) and d for many important problems including Odd Cycle Transversal and Almost 2-SAT. More specifically, we can choose f(k) as a single exponential (4^k) and d as one, that is, linear in the input size. To the best of our knowledge, our algorithms achieve linear time complexity for the first time for these problems. To obtain our algorithms for these problems, we consider a large class of integer programs, called BIP2. Then we show that, in linear time, we can reduce BIP2 to Vertex Cover Above LP preserving the parameter k, and we can compute an optimal LP solution for Vertex Cover Above LP using network flow. Then, we perform an exhaustive search by fixing half-integral values in the optimal LP solution for Vertex Cover Above LP. A bottleneck here is that we need to recompute an LP optimal solution after branching. To address this issue, we exploit network flow to update the optimal LP solution in linear time.
BibTeX
@inproceedings{iwata2014linear,
  author = {Yoichi Iwata and Keigo Oka and Yuichi Yoshida},
  title = {{Linear-Time FPT Algorithms via Network Flow}},
  booktitle = {SODA},
  year = {2014},
  doi = {10.1137/1.9781611973402.127},
}
Figure