On the approximate compressibility of connected vertex cover

DOI10.1007/s00453-020-00708-4zbMath1455.68144arXiv1905.03379OpenAlexW2944564962MaRDI QIDQ2006945

Saket Saurabh, M. S. Ramanujan, Diptapriyo Majumdar

Publication date: 12 October 2020

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

parameterized complexitykernelizationconnected vertex coverapproximate kernelization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

\(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Extension and its price for the connected vertex cover problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Infeasibility of instance compression and succinct PCPs for NP
• Graph operations characterizing rank-width
• On problems without polynomial kernels
• Depth-first search and the vertex cover problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Algorithmic graph theory and perfect graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Revisiting connected vertex cover: FPT algorithms and lossy kernels
• Polynomial kernels for vertex cover parameterized by small degree modulators
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• A completeness theory for polynomial (Turing) kernelization
• On the hardness of losing width
• Parametrized complexity theory.
• Rank-width and vertex-minors
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Kernelization – Preprocessing with a Guarantee
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Vertex Cover Structural Parameterization Revisited
• New Limits to Classical and Quantum Instance Compression
• Approximation and Kernelization for Chordal Vertex Deletion
• Kernelization
• Kernelization Lower Bounds Through Colors and IDs
• Lossy kernelization
• Kernelization Lower Bounds by Cross-Composition
• Smaller Parameters for Vertex Cover Kernelization
• Representative Sets and Irrelevant Vertices
• On the Relationship Between Clique-Width and Treewidth
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms

This page was built for publication: On the approximate compressibility of connected vertex cover