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

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

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 |