Connected k-domination no-kernel at twin-width 4

Open problem: no-kernel lower bound at twin-width 4 for Connected/Total k-Dominating Set · arXiv:2107.02882

arXiv Informal medium confidence— first stated 2021-09-14

Authors: Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant

Status open high confidence

The source paper (arXiv:2107.02882) establishes that Connected k-Dominating Set and Total k-Dominating Set have no polynomial kernel on graphs of bounded twin-width via local gadget modifications of their main reduction, but with a worse upper bound on the twin-width than 4. The open problem asks whether the twin-width bound can be brought down to exactly 4 (matching the result for plain k-Dominating Set in Theorem 1). No follow-up paper resolving this specific question was found in five targeted web searches covering the period 2021–2026.

Reviewer notes. No follow-up paper resolving or partially addressing this open problem was found. The MFCS 2025 paper on dominating set variants and twin-width (LIPIcs.MFCS.2025.13) addresses FPT algorithms rather than kernelization lower bounds and is unrelated. The conjecture is open with high confidence.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Can one show that Connected $k$-Dominating Set and Total $k$-Dominating Set on graphs of twin-width at most $4$ do not admit a polynomial kernel (unless $\mathrm{coNP} \subseteq \mathrm{NP/poly}$), even when a $4$-sequence of the graph is given?

Context

The authors establish via local gadget modifications of their main reduction (Theorem 1) that Connected $k$-Dominating Set and Total $k$-Dominating Set have no polynomial kernel on graphs of bounded twin-width, but with a worse upper bound on the twin-width than 4. Bringing the twin-width bound down to 4—as achieved for plain $k$-Dominating Set in Theorem 1—would require additional work.

Notes. Implicit open problem stated in prose: 'More work would be necessary to get the lower bound for twin-width at most 4.' Confirmed by Table 1, which lists no 'no PK' entry for Connected k-Dominating Set at twin-width at most 4. PDF source — math notation may be partially garbled.

Source paper

Twin-width and polynomial kernels
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant · 2021-09-14
https://arxiv.org/abs/2107.02882 PDF source