Approximation and kernelization for chordal vertex deletion

B.M.P. Jansen; M. Pilipczuk

doi:10.1137/1.9781611974782.91

Approximation and kernelization for chordal vertex deletion

B.M.P. Jansen, M. Pilipczuk

Algorithms, Geometry and Applications

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

15 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 language	English
Title of host publication	Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 16-19 January 2017, Barcelona, Spain
Editors	Philip N. Klein
Place of Publication	s.l.
Publisher	Society for Industrial and Applied Mathematics (SIAM)
Pages	1399-1418
Number of pages	20
ISBN (Electronic)	978-1-61197-478-2
DOIs	https://doi.org/10.1137/1.9781611974782.91
Publication status	Published - 2017
Event	28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) - Barcelona, Spain Duration: 16 Jan 2017 → 19 Jan 2017 Conference number: 28

Conference

Conference	28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
Abbreviated title	SODA 2017
Country/Territory	Spain
City	Barcelona
Period	16/01/17 → 19/01/17

Access to Document

10.1137/1.9781611974782.91

Cite this

@inproceedings{d324136fe21d44d698ddfe115953863d,

title = "Approximation and kernelization for chordal vertex deletion",

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",

author = "B.M.P. Jansen and M. Pilipczuk",

year = "2017",

doi = "10.1137/1.9781611974782.91",

language = "English",

pages = "1399--1418",

editor = "Klein, {Philip N.}",

booktitle = "Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 16-19 January 2017, Barcelona, Spain",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

address = "United States",

note = "28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), SODA 2017 ; Conference date: 16-01-2017 Through 19-01-2017",

}

Jansen, BMP & Pilipczuk, M 2017, Approximation and kernelization for chordal vertex deletion. in PN Klein (ed.), Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 16-19 January 2017, Barcelona, Spain. Society for Industrial and Applied Mathematics (SIAM), s.l., pp. 1399-1418, 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 16/01/17. https://doi.org/10.1137/1.9781611974782.91

Approximation and kernelization for chordal vertex deletion. / Jansen, B.M.P.; Pilipczuk, M.

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 16-19 January 2017, Barcelona, Spain. ed. / Philip N. Klein. s.l. : Society for Industrial and Applied Mathematics (SIAM), 2017. p. 1399-1418.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximation and kernelization for chordal vertex deletion

AU - Jansen, B.M.P.

AU - Pilipczuk, M.

N1 - Conference code: 28

PY - 2017

Y1 - 2017

N2 - 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

AB - 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

UR - http://www.scopus.com/inward/record.url?scp=85016175307&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974782.91

DO - 10.1137/1.9781611974782.91

M3 - Conference contribution

SP - 1399

EP - 1418

BT - Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 16-19 January 2017, Barcelona, Spain

A2 - Klein, Philip N.

PB - Society for Industrial and Applied Mathematics (SIAM)

CY - s.l.

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)

Y2 - 16 January 2017 through 19 January 2017

ER -

Approximation and kernelization for chordal vertex deletion

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this