Faster Parameterized Algorithms Using Linear Programming
From MaRDI portal
Publication:4962173
DOI10.1145/2566616zbMath1398.68254arXiv1203.0833OpenAlexW2166115470MaRDI QIDQ4962173
N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh, Daniel Lokshtanov
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
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (67)
Autarkies and Persistencies for QUBO ⋮ Parameterizing edge modification problems above lower bounds ⋮ A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ A Faster Parameterized Algorithm for Group Feedback Edge Set ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\) ⋮ Structural parameterizations with modulator oblivion ⋮ On approximability of optimization problems related to red/blue-split graphs ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Parameterized and exact algorithms for class domination coloring ⋮ List-coloring -- parameterizing from triviality ⋮ Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion} ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Odd cycle transversal in mixed graphs ⋮ Parameterized complexity of MaxSat above average ⋮ Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ Hitting Selected (Odd) Cycles ⋮ A polynomial kernel for 3-leaf power deletion ⋮ An Updated Experimental Evaluation of Graph Bipartization Methods ⋮ Perfect forests in graphs and their extensions ⋮ Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes ⋮ Detours in directed graphs ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ 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 ⋮ Unnamed Item ⋮ Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Unnamed Item ⋮ Going Far from Degeneracy ⋮ Another disjoint compression algorithm for odd cycle transversal ⋮ A faster FPT algorithm for bipartite contraction ⋮ Backdoor Sets for CSP. ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ 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 ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Edge bipartization faster than \(2^k\) ⋮ Quadratic vertex kernel for split vertex deletion ⋮ List H-coloring a graph by removing few vertices ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximability of clique transversal in perfect graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Balanced stable marriage: how close is close enough? ⋮ Improved analysis of highest-degree branching for feedback vertex set ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ Faster graph bipartization ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ Unnamed Item ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ Tractability of König edge deletion problems ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints ⋮ Above guarantee parameterization for vertex cover on graphs with maximum degree 4 ⋮ Faster parameterized algorithms for deletion to split graphs
This page was built for publication: Faster Parameterized Algorithms Using Linear Programming
