Abstract
We study the existence of polynomial kernels for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twinwidth. It was previously observed in [Bonnet et al., ICALP'21] that the problem kIndependent Set allows no polynomial kernel on graph of bounded twinwidth by a very simple argument, which extends to several other problems such as kIndependent Dominating Set, kPath, kInduced Path, kInduced Matching. In this work, we examine the kDominating Set and variants of kVertex Cover for the existence of polynomial kernels.
As a main result, we show that kDominating Set does not admit a polynomial kernel on graphs of twinwidth at most 4 under a standard complexitytheoretic assumption. The reduction is intricate, especially due to the effort to bring the twinwidth down to 4, and it can be tweaked to work for Connected kDominating Set and Total kDominating Set with a slightly worse bound on the twinwidth.
On the positive side, we obtain a simple quadratic vertex kernel for Connected kVertex Cover and Capacitated kVertex Cover on graphs of bounded twinwidth. These kernels rely on that graphs of bounded twinwidth have VapnikChervonenkis (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 twinwidth. 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 kVertex Cover.
Finally we show that deciding if a graph has twinwidth 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 twinwidth 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 = {{TwinWidth and Polynomial Kernels}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {10:110:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772167},
ISSN = {18688969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15393},
URN = {urn:nbn:de:0030drops153932},
doi = {10.4230/LIPIcs.IPEC.2021.10},
annote = {Keywords: Twinwidth, kernelization, lower bounds, Dominating Set}
}
Keywords: 

Twinwidth, 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 