Faster parameterized algorithms using linear programming

DOI10.1145/2566616MaRDI QIDQ4962173zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

parameterized algorithmsvertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Abstract: We investigate the parameterized complexity of Vertex Cover parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an $O^{\ast }((2.618{)}^k)$ algorithm for the problem. Here $k$ is the excess of the vertex cover size over the LP optimum, and we write $O^{\ast }(f(k))$ for a time complexity of the form $O(f(k)n^{O(1)})$, where $f(k)$ grows exponentially with $k$. We proceed to show that a more sophisticated branching algorithm achieves a runtime of $O^{\ast }(2.3146^k)$. Following this, using known and new reductions, we give $O^{\ast }(2.3146^k)$ algorithms for the parameterized versions of Above Guarantee Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion and Almost 2-SAT, and an $O^{\ast }(1.5214^k)$ algorithm for Ko"nig Vertex Deletion, Vertex Cover Param by OCT and Vertex Cover Param by KVD. These algorithms significantly improve the best known bounds for these problems. The most notable improvement is the new bound for Odd Cycle Transversal - this is the first algorithm which beats the dependence on $k$ of the seminal $O^{\ast }(3^k)$ algorithm of Reed, Smith and Vetta. Finally, using our algorithm, we obtain a kernel for the standard parameterization of Vertex Cover with at most $2k-clogk$ vertices. Our kernel is simpler than previously known kernels achieving the same size bound.

Recommendations

• LP can be a cure for parameterized problems
• A randomized polynomial kernelization for vertex cover with a smaller parameter
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• Improved Parameterized Upper Bounds for Vertex Cover

Cited in

(94)

• A general method to speed up fixed-parameter-tractable algorithms
• Improved analysis of highest-degree branching for feedback vertex set
• Above guarantee parameterization for vertex cover on graphs with maximum degree 4
• Structural parameterizations with modulator oblivion
• Distance from triviality 2.0: hybrid parameterizations
• List-coloring -- parameterizing from triviality
• Faster graph bipartization
• Revisiting connected vertex cover: FPT algorithms and lossy kernels
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Tractability of König edge deletion problems
• Fixed-parameter tractability for subset feedback set problems with parity constraints
• Faster parameterized algorithms for deletion to split graphs
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
• On approximability of optimization problems related to red/blue-split graphs
• Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
• Another disjoint compression algorithm for odd cycle transversal
• Parameterized and exact algorithms for class domination coloring
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Odd cycle transversal in mixed graphs
• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
• Half-integrality, LP-branching, and FPT algorithms
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• LP can be a cure for parameterized problems
• Parameterized and exact algorithms for class domination coloring
• A randomized polynomial kernelization for vertex cover with a smaller parameter
• A faster parameterized algorithm for Group Feedback Edge Set
• Designing FPT algorithms for cut problems using randomized contractions
• Odd multiway cut in directed acyclic graphs
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• LP-branching algorithms based on biased graphs
• The complexity of finding (approximate sized) distance-d dominating set in tournaments
• FPT algorithms for FVS parameterized by split and cluster vertex deletion sets and other parameters
• Backdoor sets for CSP
• Autarkies and Persistencies for QUBO
• Going far from degeneracy
• scientific article; zbMATH DE number 7559376 (Why is no real title available?)
• On kernelization for edge dominating set under structural parameters
• New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
• Domination above \(r\)-independence: does sparseness help?
• Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
• An Updated Experimental Evaluation of Graph Bipartization Methods
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• Odd Multiway Cut in Directed Acyclic Graphs
• Going far from degeneracy
• scientific article; zbMATH DE number 7278081 (Why is no real title available?)
• Balanced judicious bipartition is fixed-parameter tractable
• Rank vertex cover as a natural problem for algebraic compression
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• Large independent sets in triangle-free planar graphs
• Hitting selected (odd) cycles
• Linear-time FPT algorithms via network flow
• Half-integrality, LP-branching and FPT algorithms
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• Quadratic vertex kernel for split vertex deletion
• Balanced stable marriage: how close is close enough?
• The parameterized complexity of cycle packing: indifference is not an issue
• Faster exact algorithms for hard problems: A parameterized point of view
• A polynomial kernel for 3-leaf power deletion
• Perfect forests in graphs and their extensions
• Structural parameterizations with modulator oblivion
• Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
• Detours in directed graphs
• Faster algorithms for cycle hitting problems on disk graphs
• A survey of parameterized algorithms and the complexity of edge modification
• Neighborhood persistency of the linear optimization relaxation of integer linear optimization
• Turán’s Theorem Through Algorithmic Lens
• Long directed detours: reduction to 2-disjoint paths
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Approximating long cycle above Dirac's guarantee
• Search-space reduction via essential vertices
• Exact and parameterized algorithms for the independent cutset problem
• Edge bipartization faster than \(2^k\)
• When recursion is better than iteration: a linear-time algorithm for directed acyclicity with few error vertices
• Dynamic programming on bipartite tree decompositions
• Neighborhood persistency of the linear optimization relaxation of integer linear optimization
• Eliminating crossings in ordered graphs
• A faster algorithm for vertex cover parameterized by solution size
• Almost consistent systems of linear equations
• Bipartizing (pseudo-)disk graphs: approximation with a ratio better than 3
• Dynamic programming on bipartite tree decompositions
• Odd cycle transversal on P₅-free graphs in polynomial time
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• Vertex cover and feedback vertex set above and below structural guarantees
• Towards exact structural thresholds for parameterized complexity
• Search-space reduction via essential vertices
• Roman cycle hitting set
• Cluster editing parameterized above modification-disjoint P₃-packings
• Cluster editing parameterized above modification-disjoint P₃-Packings
• Approximability of clique transversal in perfect graphs
• Hitting meets packing: how hard can it be?
• Preprocessing to reduce the search space for odd cycle transversal
• A fast algorithm for maximum satisfiability above half number of clauses
• Efficient parameterized approximation
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover

This page was built for publication: Faster parameterized algorithms using linear programming

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