Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel

DOI10.1137/21M1400766zbMath1503.05095arXiv2004.12865OpenAlexW4309757171MaRDI QIDQ5048303

Bart M. P. Jansen, Marin Bougeret, Ignasi Sau

Publication date: 15 November 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

vertex coverparameterized complexitypolynomial kernelstructural parameterizationbridge-depth

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Kernelization for feedback vertex set via elimination distance to a forest ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Parameterized complexity of computing maximum minimal blocking and hitting sets

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Graph isomorphism parameterized by elimination distance to bounded degree
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• Graph minors. XX: Wagner's conjecture
• Graph minors. V. Excluding a planar graph
• A partial k-arboretum of graphs with bounded treewidth
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Width, depth, and space: tradeoffs between branching and dynamic programming
• Polynomial kernels for vertex cover parameterized by small degree modulators
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• On the hardness of losing width
• Parametrized complexity theory.
• Tree-depth, subgraph coloring and homomorphism bounds
• Hitting Forbidden Minors: Approximation and Kernelization
• Kernelization – Preprocessing with a Guarantee
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Vertex Cover Structural Parameterization Revisited
• Vertex packings: Structural properties and algorithms
• Kernelization
• On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
• Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
• Smaller Parameters for Vertex Cover Kernelization
• A tight Erdős-Pósa function for planar minors
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Elimination distances, blocking sets, and kernels for Vertex Cover
• The Erdős-Pósa property for odd cycles in highly connected graphs
• What Is Known About Vertex Cover Kernelization?

This page was built for publication: Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel