Polynomial kernels for vertex cover parameterized by small degree modulators

DOI10.1007/s00224-018-9858-1zbMath1419.05179OpenAlexW2790946280MaRDI QIDQ2322700

Venkatesh Raman, Diptapriyo Majumdar, Saket Saurabh

Publication date: 5 September 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-018-9858-1

zbMATH Keywords

vertex coverparameterized complexitykernelizationstructural parameterizationexpansion lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Structural parameterizations with modulator oblivion ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ Unnamed Item ⋮ On the approximate compressibility of connected vertex cover ⋮ Extension and its price for the connected vertex cover problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Fundamentals of parameterized complexity
• A probabilistic approach to problems parameterized above or below tight bounds
• Improved upper bounds for vertex cover
• The complexity ecology of parameters: An illustration using bounded max leaf number
• A kernelization algorithm for \(d\)-hitting set
• Parameterized complexity of vertex colouring
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT
• On the hardness of losing width
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Hitting Forbidden Minors: Approximation and Kernelization
• Improved Parameterized Algorithms for above Average Constraint Satisfaction
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• On the Kernelization Complexity of Problems on Graphs without Long Odd Cycles
• Vertex Cover Structural Parameterization Revisited
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Vertex packings: Structural properties and algorithms
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
• Faster Parameterized Algorithms Using Linear Programming
• Kernelization Lower Bounds by Cross-Composition
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs
• Smaller Parameters for Vertex Cover Kernelization
• Representative Sets and Irrelevant Vertices
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms

This page was built for publication: Polynomial kernels for vertex cover parameterized by small degree modulators