Linear-time FPT algorithms via network flow

DOI10.1137/1.9781611973402.127MaRDI QIDQ5384089zbMATH OpenOpenAlexFDO

Authors Yoichi Iwata, Keigo Oka, Yuichi Yoshida

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.4927

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Linear programming (90C05)

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.

Recommendations

• Faster parameterized algorithms using linear programming
• LP can be a cure for parameterized problems
• Half-integrality, LP-branching, and FPT algorithms
• Linear time parameterized algorithms for \textsc{Subset Feedback Vertex Set}
• Fixed-parameter algorithms in analysis of heuristics for extracting networks in linear programs

Cited in

(18)

• Fixed-parameter tractability for subset feedback set problems with parity constraints
• Odd cycle transversal in mixed graphs
• Half-integrality, LP-branching, and FPT algorithms
• Odd multiway cut in directed acyclic graphs
• Linear time parameterized algorithms for subset feedback vertex set
• Fixed-parameter algorithms in analysis of heuristics for extracting networks in linear programs
• Estimating the Size of Branch-and-Bound Trees
• Data Reduction for Maximum Matching on Real-World Graphs
• An Updated Experimental Evaluation of Graph Bipartization Methods
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• scientific article; zbMATH DE number 7278081 (Why is no real title available?)
• Why is maximum clique often easy in practice?
• Hitting selected (odd) cycles
• Half-integrality, LP-branching and FPT algorithms
• On the parallel parameterized complexity of MaxSAT variants
• Odd cycle transversal on P₅-free graphs in polynomial time
• Boundaried kernelization
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover

This page was built for publication: Linear-time FPT algorithms via network flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384089)