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.MFCS.2021.45
URN: urn:nbn:de:0030-drops-144851
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14485/
Go to the corresponding LIPIcs Volume Portal

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

A Cubic Vertex-Kernel for Trivially Perfect Editing

pdf-format:
LIPIcs-MFCS-2021-45.pdf (0.7 MB)

Abstract

We consider the Trivially Perfect 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 trivially perfect graph. The related Trivially Perfect Completion and Trivially Perfect Deletion problems are obtained by only allowing edge additions or edge deletions, respectively. Trivially perfect graphs are both chordal and cographs, and have applications related to the tree-depth width parameter and to social network analysis. All variants of the problem are known to be NP-complete [Burzyn et al., 2006; James Nastos and Yong Gao, 2013] and to admit so-called polynomial kernels [Pål Grønås Drange and Michał Pilipczuk, 2018; Jiong Guo, 2007]. More precisely, the existence of an O(k³) vertex-kernel for Trivially Perfect Completion was announced by Guo [Jiong Guo, 2007] but without a stand-alone proof. More recently, Drange and Pilipczuk [Pål Grønås Drange and Michał Pilipczuk, 2018] provided O(k⁷) vertex-kernels for these problems and left open the existence of cubic vertex-kernels. In this work, we answer positively to this question for all three variants of the problem.

BibTeX - Entry

@InProceedings{dumas_et_al:LIPIcs.MFCS.2021.45,
  author =	{Dumas, Ma\"{e}l and Perez, Anthony and Todinca, Ioan},
  title =	{{A Cubic Vertex-Kernel for Trivially Perfect Editing}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14485},
  URN =		{urn:nbn:de:0030-drops-144851},
  doi =		{10.4230/LIPIcs.MFCS.2021.45},
  annote =	{Keywords: Parameterized complexity, kernelization algorithms, graph modification, trivially perfect graphs}
}

Keywords: Parameterized complexity, kernelization algorithms, graph modification, trivially perfect graphs
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

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