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

Cao, Yixin ; Ke, Yuping

Improved Kernels for Edge Modification Problems

pdf-format:
LIPIcs-IPEC-2021-13.pdf (0.7 MB)

Abstract

In an edge modification problem, we are asked to modify at most k edges of a given graph to make the graph satisfy a certain property. Depending on the operations allowed, we have the completion problems and the edge deletion problems. A great amount of efforts have been devoted to understanding the kernelization complexity of these problems. We revisit several well-studied edge modification problems, and develop improved kernels for them:
- a 2 k-vertex kernel for the cluster edge deletion problem,
- a 3 k²-vertex kernel for the trivially perfect completion problem,
- a 5 k^{1.5}-vertex kernel for the split completion problem and the split edge deletion problem, and
- a 5 k^{1.5}-vertex kernel for the pseudo-split completion problem and the pseudo-split edge deletion problem. Moreover, our kernels for split completion and pseudo-split completion have only O(k^{2.5}) edges. Our results also include a 2 k-vertex kernel for the strong triadic closure problem, which is related to cluster edge deletion.

BibTeX - Entry

@InProceedings{cao_et_al:LIPIcs.IPEC.2021.13,
  author =	{Cao, Yixin and Ke, Yuping},
  title =	{{Improved Kernels for Edge Modification Problems}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{13:1--13:14},
  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/15396},
  URN =		{urn:nbn:de:0030-drops-153965},
  doi =		{10.4230/LIPIcs.IPEC.2021.13},
  annote =	{Keywords: Kernelization, edge modification, cluster, trivially perfect graphs, split graphs}
}

Keywords: Kernelization, edge modification, cluster, trivially perfect graphs, split 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