DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2021.13

Improved Kernels for Edge Modification Problems

Authors: Yixin Cao and Yuping Ke

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

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.

Cite as

Yixin Cao and Yuping Ke. Improved Kernels for Edge Modification Problems. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.IPEC.2021.13},
  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}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2017.22

Vertex Deletion Problems on Chordal Graphs

Authors: Yixin Cao, Yuping Ke, Yota Otachi, and Jie You

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract

Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.

Cite as

Yixin Cao, Yuping Ke, Yota Otachi, and Jie You. Vertex Deletion Problems on Chordal Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.FSTTCS.2017.22,
  author =	{Cao, Yixin and Ke, Yuping and Otachi, Yota and You, Jie},
  title =	{{Vertex Deletion Problems on Chordal Graphs}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.22},
  URN =		{urn:nbn:de:0030-drops-83799},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.22},
  annote =	{Keywords: vertex deletion problem, maximum subgraph, chordal graph, (unit) interval graph, split graph, hereditary property, NP-complete, polynomial-time algori}
}

Search Results

Documents authored by Ke, Yuping

Improved Kernels for Edge Modification Problems

Abstract

Cite as

Vertex Deletion Problems on Chordal Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message