Approximation and kernelization for chordal vertex deletion

DOI10.1137/1.9781611974782.91MaRDI QIDQ4575834zbMATH OpenOpenAlexFDO

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)

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

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)

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].

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

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
• Chordal deletion is fixed-parameter tractable
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Quadratic vertex kernel for split vertex deletion
• Structural parameterizations with modulator oblivion
• Vertex deletion problems on chordal graphs
• Structural parameterizations with modulator oblivion
• 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)