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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15468/
Koana, Tomohiro ;
Komusiewicz, Christian ;
Sommer, Frank
Essentially Tight Kernels For (Weakly) Closed Graphs
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 |
