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.10
URN: urn:nbn:de:0030-drops-153932
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15393/
Bonnet, Édouard ;
Kim, Eun Jung ;
Reinald, Amadeus ;
Thomassé, Stéphan ;
Watrigant, Rémi
Twin-Width and Polynomial Kernels
Abstract
We study the existence of polynomial kernels for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. It was previously observed in [Bonnet et al., ICALP'21] that the problem k-Independent Set allows no polynomial kernel on graph of bounded twin-width by a very simple argument, which extends to several other problems such as k-Independent Dominating Set, k-Path, k-Induced Path, k-Induced Matching. In this work, we examine the k-Dominating Set and variants of k-Vertex Cover for the existence of polynomial kernels.
As a main result, we show that k-Dominating Set does not admit a polynomial kernel on graphs of twin-width at most 4 under a standard complexity-theoretic assumption. The reduction is intricate, especially due to the effort to bring the twin-width down to 4, and it can be tweaked to work for Connected k-Dominating Set and Total k-Dominating Set with a slightly worse bound on the twin-width.
On the positive side, we obtain a simple quadratic vertex kernel for Connected k-Vertex Cover and Capacitated k-Vertex Cover on graphs of bounded twin-width. These kernels rely on that graphs of bounded twin-width have Vapnik-Chervonenkis (VC) density 1, that is, for any vertex set X, the number of distinct neighborhoods in X is at most c⋅|X|, where c is a constant depending only on the twin-width. Interestingly the kernel applies to any graph class of VC density 1, and does not require a witness sequence. We also present a more intricate O(k^{1.5}) vertex kernel for Connected k-Vertex Cover.
Finally we show that deciding if a graph has twin-width at most 1 can be done in polynomial time, and observe that most graph optimization/decision problems can be solved in polynomial time on graphs of twin-width at most 1.
BibTeX - Entry
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2021.10,
author = {Bonnet, \'{E}douard and Kim, Eun Jung and Reinald, Amadeus and Thomass\'{e}, St\'{e}phan and Watrigant, R\'{e}mi},
title = {{Twin-Width and Polynomial Kernels}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {10:1--10:16},
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/15393},
URN = {urn:nbn:de:0030-drops-153932},
doi = {10.4230/LIPIcs.IPEC.2021.10},
annote = {Keywords: Twin-width, kernelization, lower bounds, Dominating Set}
}
|
Keywords: |
|
Twin-width, kernelization, lower bounds, Dominating Set |
|
Collection: |
|
16th International Symposium on Parameterized and Exact Computation (IPEC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
22.11.2021 |
