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.ISAAC.2021.35
URN: urn:nbn:de:0030-drops-154681
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15468/
 Go to the corresponding LIPIcs Volume Portal

Essentially Tight Kernels For (Weakly) Closed Graphs

 pdf-format:

Abstract

We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number c and weak closure number γ [Fox et al., SICOMP 2020] in addition to the standard parameter solution size k. The weak closure number γ of a graph is upper-bounded by the minimum of its closure number c and its degeneracy d. For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size k^𝒪(γ), k^𝒪(γ), and (γk)^𝒪(γ), respectively. This extends previous results on the kernelization of these problems on degenerate graphs. These kernels are essentially tight as these problems are unlikely to admit kernels of size k^o(γ) by previous results on their kernelization complexity in degenerate graphs [Cygan et al., ACM TALG 2017]. For Capacitated Vertex Cover, we show that even a kernel of size k^o(c) is unlikely. In contrast, for Connected Vertex Cover, we obtain a problem kernel with 𝒪(ck²) vertices. Moreover, we prove that searching for an induced subgraph of order at least k belonging to a hereditary graph class 𝒢 admits a kernel of size k^𝒪(γ) when 𝒢 contains all complete and all edgeless graphs. Finally, we provide lower bounds for the kernelization of Independent Set on graphs with constant closure number c and kernels for Dominating Set on weakly closed split graphs and weakly closed bipartite graphs.

BibTeX - Entry

@InProceedings{koana_et_al:LIPIcs.ISAAC.2021.35,
author =	{Koana, Tomohiro and Komusiewicz, Christian and Sommer, Frank},
title =	{{Essentially Tight Kernels For (Weakly) Closed Graphs}},
booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages =	{35:1--35:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-214-3},
ISSN =	{1868-8969},
year =	{2021},
volume =	{212},
editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address =	{Dagstuhl, Germany},
URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15468},
URN =		{urn:nbn:de:0030-drops-154681},
doi =		{10.4230/LIPIcs.ISAAC.2021.35},
annote =	{Keywords: Fixed-parameter tractability, kernelization, c-closure, weak \gamma-closure, Independent Set, Induced Matching, Connected Vertex Cover, Ramsey numbers, Dominating Set}
}

 Keywords: Fixed-parameter tractability, kernelization, c-closure, weak γ-closure, Independent Set, Induced Matching, Connected Vertex Cover, Ramsey numbers, Dominating Set Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021) Issue Date: 2021 Date of publication: 30.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy