2026-07-22T10:25:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15393 2024-03-06T10:55:38Z ddc:004 open_access

Twin-Width and Polynomial Kernels Bonnet, Édouard Kim, Eun Jung Reinald, Amadeus Thomassé, Stéphan Watrigant, Rémi Twin-width kernelization lower bounds Dominating Set 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Eun Jung Kim and Amadeus Reinald and Stéphan Thomassé and Rémi Watrigant 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.10 urn:nbn:de:0030-drops-153932 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.10 eng https://creativecommons.org/licenses/by/4.0/legalcode