Approximation and kernelization for chordal vertex deletion

B.M.P. Jansen, M. Pilipczuk

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

14 Citations (Scopus)

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. Using a new Erdos-Posa type packing/covering duality for holes in nearly-chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of ChVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem of Marx from 2006 [WG 2006, LNCS 4271, 37–48]. To obtain the kernelization, we develop the first poly(oPT)- approximation algorithm for ChVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k4 log2 k).

Read More: http://epubs.siam.org/doi/10.1137/1.9781611974782.91
Original languageEnglish
Title of host publicationProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 16-19 January 2017, Barcelona, Spain
EditorsPhilip N. Klein
Place of Publications.l.
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages1399-1418
Number of pages20
ISBN (Electronic)978-1-61197-478-2
DOIs
Publication statusPublished - 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) - Barcelona, Spain
Duration: 16 Jan 201719 Jan 2017
Conference number: 28

Conference

Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
Abbreviated titleSODA 2017
CountrySpain
CityBarcelona
Period16/01/1719/01/17

Fingerprint Dive into the research topics of 'Approximation and kernelization for chordal vertex deletion'. Together they form a unique fingerprint.

Cite this