Metraipolis › archive › dc_1df84ab9f810
A Dichotomy for Terminal Cyclability — arXiv:2611.06234
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06234
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:37.948Z
- SHA-256 of the archived text
70ad018a5bc4f166a0a20cf811ec90e145242c88099d79f3b469c71b033e4868- Stable URL of this page
https://metraipolis.com/documento/dc_1df84ab9f810
How to cite
A Dichotomy for Terminal Cyclability — arXiv:2611.06234 — arXiv (en), https://arxiv.org/abs/2611.06234 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1df84ab9f810 (Metraipolis archive dc_1df84ab9f810, sha256 70ad018a5bc4f166a0a20cf811ec90e145242c88099d79f3b469c71b033e4868)
BibTeX
@misc{dc1df84ab9f810,
title = {A Dichotomy for Terminal Cyclability — arXiv:2611.06234},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06234},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1df84ab9f810; sha256 70ad018a5bc4f166a0a20cf811ec90e145242c88099d79f3b469c71b033e4868},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06234. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Given an undirected graph $G$ and a set $R \subseteq V(G)$ of terminals, Terminal Cyclability asks whether $G$ contains a simple cycle visiting every vertex of $R$. We establish a complexity dichotomy for this problem on red-minor-closed classes of annotated graphs. In particular, we show that Terminal Cyclability is polynomial-time solvable on every such class excluding any annotated planar graph. The problem is NP-complete whenever the class contains all annotated planar graphs. More precisely, we give an $|G|^{2^{\mathbf{poly}(b)}}$-time algorithm, where $b$ is the bidimensionality of $(G,R)$. Our main technical contribution is the introduction of a weak irrelevant vertex rule. Rather than removing irrelevant vertices until the treewidth becomes constant, we only remove irrelevant vertices until the treewidth is logarithmic in the graph size. Such a weakening is necessary as a parameter-only treewidth threshold for an irrelevant vertex rule in this setting is known to be impossible to realise. Combined with a single-exponential algorithm for Terminal Cyclability parameterized by treewidth, this yields the polynomial-time algorithm for our dichotomy.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.06234 — 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-11-05T18:21:04.027Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).