License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.17
URN: urn:nbn:de:0030-drops-154005
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15400/
Go to the corresponding LIPIcs Volume Portal

Dumas, Maël ; Perez, Anthony ; Todinca, Ioan

Polynomial Kernels for Strictly Chordal Edge Modification Problems

pdf-format:
LIPIcs-IPEC-2021-17.pdf (0.8 MB)

Abstract

We consider the Strictly Chordal Editing problem, where one is given an undirected graph G = (V,E) and a parameter k ∈ ℕ and seeks to edit (add or delete) at most k edges from G to obtain a strictly chordal graph. Problems Strictly Chordal Completion and Strictly Chordal Deletion are defined similarly, by only allowing edge additions for the former, and only edge deletions for the latter. Strictly chordal graphs are a generalization of 3-leaf power graphs and a subclass of 4-leaf power graphs. They can be defined, e.g., as dart and gem-free chordal graphs. We prove the NP-completeness for all three variants of the problem and provide an O(k³) vertex-kernel for the completion version and O(k⁴) vertex-kernels for the two others.

BibTeX - Entry

@InProceedings{dumas_et_al:LIPIcs.IPEC.2021.17,
  author =	{Dumas, Ma\"{e}l and Perez, Anthony and Todinca, Ioan},
  title =	{{Polynomial Kernels for Strictly Chordal Edge Modification Problems}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15400},
  URN =		{urn:nbn:de:0030-drops-154005},
  doi =		{10.4230/LIPIcs.IPEC.2021.17},
  annote =	{Keywords: Parameterized complexity, kernelization algorithms, graph modification, strictly chordal graphs}
}

Keywords: Parameterized complexity, kernelization algorithms, graph modification, strictly chordal graphs
Collection: 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Issue Date: 2021
Date of publication: 22.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI