Vertex Cover Structural Parameterization Revisited

DOI10.1007/978-3-662-53536-3_15zbMath1417.05206arXiv1603.00770OpenAlexW2292947609WikidataQ60488384 ScholiaQ60488384MaRDI QIDQ3181056

Torstein J. F. Strømme, Fedor V. Fomin

Publication date: 22 December 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel, Vertex Cover Structural Parameterization Revisited, Lower bounds for protrusion replacement by counting equivalence classes, Elimination Distances, Blocking Sets, and Kernels for Vertex Cover, What Is Known About Vertex Cover Kernelization?, Polynomial kernels for hitting forbidden minors under structural parameterizations, Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations., An improved FPT algorithm for almost forest deletion problem, On the approximate compressibility of connected vertex cover, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, Polynomial kernels for vertex cover parameterized by small degree modulators, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs, Smaller Parameters for Vertex Cover Kernelization

Cites Work

• Unnamed Item
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• A unified approximation algorithm for node-deletion problems
• On the hardness of losing width
• Vertex Cover Structural Parameterization Revisited
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses