Approximation and kernelization for chordal vertex deletion

DOI10.1137/1.9781611974782.91zbMATH Open1410.68300arXiv1605.03001OpenAlexW2374265145MaRDI QIDQ4575834FDOQ4575834

Authors: Bart M. P. Jansen, Marcin Pilipczuk 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by the solution size, as well as poly(opt) approximation algorithm. The first result answers an open problem of Marx from 2006 [WG 2006, LNCS 4271, 37-48].

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

Recommendations

• Approximation and kernelization for chordal vertex deletion
• Feedback vertex set inspired kernel for chordal vertex deletion
• Feedback vertex set inspired kernel for chordal vertex deletion
• Chordal deletion is fixed-parameter tractable
• Chordal Deletion Is Fixed-Parameter Tractable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Paths and cycles (05C38)

Cited In (29)

• Parameterized complexity of vertex deletion into perfect graph classes
• A polynomial kernel for block graph deletion
• Deletion in Abstract Voronoi Diagrams in Expected Linear Time.
• On the Erdős–Pósa Property for Long Holes in \(\boldsymbol{C_4}\)-Free Graphs
• Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems
• Unit interval vertex deletion: fewer vertices are relevant
• A vertex incremental approach for maintaining chordality
• Chordal Deletion Is Fixed-Parameter Tractable
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Feedback vertex set inspired kernel for chordal vertex deletion
• Approximation and kernelization for chordal vertex deletion
• Feedback vertex set inspired kernel for chordal vertex deletion
• Erdős-Pósa property of chordless cycles and its applications
• Vertex deletion problems on chordal graphs
• Parameterized complexity of vertex deletion into perfect graph classes
• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Quadratic vertex kernel for split vertex deletion
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Chordal deletion is fixed-parameter tractable
• Structural parameterizations with modulator oblivion
• Structural parameterizations with modulator oblivion
• Vertex deletion problems on chordal graphs
• Kernelization through Tidying
• Polynomial Kernel for Interval Vertex Deletion
• Packing and covering induced subdivisions
• A polynomial kernel for block graph deletion
• Recent techniques and results on the Erdős-Pósa property
• A polynomial kernel for bipartite permutation vertex deletion

This page was built for publication: Approximation and kernelization for chordal vertex deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575834)