Metraipolis › archive › dc_2e6990731ddc
Lower Bounds for Domination-Type Problems Parameterized by Rank-Width — arXiv:2608.18854
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.18854
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T14:08:12.512Z
- SHA-256 of the archived text
260b5c72110504bde5b68591f6d456884036e65afc0409a5f799181b79b5ed33- Stable URL of this page
https://metraipolis.com/documento/dc_2e6990731ddc
How to cite
Lower Bounds for Domination-Type Problems Parameterized by Rank-Width — arXiv:2608.18854 — arXiv (en), https://arxiv.org/abs/2608.18854 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2e6990731ddc (Metraipolis archive dc_2e6990731ddc, sha256 260b5c72110504bde5b68591f6d456884036e65afc0409a5f799181b79b5ed33)
BibTeX
@misc{dc2e6990731ddc,
title = {Lower Bounds for Domination-Type Problems Parameterized by Rank-Width — arXiv:2608.18854},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.18854},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2e6990731ddc; sha256 260b5c72110504bde5b68591f6d456884036e65afc0409a5f799181b79b5ed33},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.18854. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite \((\sigma,\rho)\)-problems and of Bergougnoux and Kanté (\emph{SIAM J. Discrete Math.}, 2021) for Connected Dominating Set run in \(2^{O(w^2)}n^{O(1)}\) time. Bergougnoux, Korhonen, and Nederlof (STACS 2023) proved a matching lower bound under the Exponential Time Hypothesis (ETH) for \emph{Weighted} Dominating Set, but left the unweighted problem open. We prove that, unless ETH fails, Dominating Set admits no \(2^{o(w^2)}n^{O(1)}\)-time algorithm, even on split graphs and, separately, on bipartite graphs of diameter at most four, and even with a rank-decomposition or witnessing vertex order supplied. The proof replaces the earlier weights by a two-guard gadget and uses a low-rank equality gadget to carry \(k^2\) assignment bits through cuts of rank \(O(k)\). The construction also gives the same lower bound for Independent, Connected, and Total Dominating Set on restricted graph classes and applies to a broad family of \((\sigma,\rho)\)-set problems. This family includes cases in which \(\sigma\) is neither finite nor cofinite and contains the entire nontrivial cofinite--cofinite minimization regime. Every solution within the target budget has target size and corresponds bijectively to a satisfying assignment. Under the counting Exponential Time Hypothesis (\(\#\mathrm{ETH}\)), the same bounds therefore hold for counting solutions of size at most or exactly the target. Together with the known algorithms, our results show that the quadratic dependence on the rank-width \(w\) is optimal up to constant factors in the exponent for the classical problems above and throughout the covered finite/cofinite regime.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-20 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.18854 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T14:07:50.833Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-20?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).