Linear-time FPT algorithms via network flow

DOI10.1137/1.9781611973402.127zbMATH Open1423.68572arXiv1307.4927OpenAlexW2952587811MaRDI QIDQ5384089FDOQ5384089

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)

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.

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

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

Mathematics Subject Classification ID

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

Cited In (16)

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

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)