Metraipolis › archive › dc_d0d1becd83eb
Revisiting the directed pathwidth of h-semicomplete digraphs — arXiv:2610.41840
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.41840
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T08:18:41.436Z
- SHA-256 of the archived text
0b5de4d4a71763d733e07b84ec326fc674c5a295aa2908eb17715ceefd9f59d0- Stable URL of this page
https://metraipolis.com/documento/dc_d0d1becd83eb
How to cite
Revisiting the directed pathwidth of h-semicomplete digraphs — arXiv:2610.41840 — arXiv (en), https://arxiv.org/abs/2610.41840 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d0d1becd83eb (Metraipolis archive dc_d0d1becd83eb, sha256 0b5de4d4a71763d733e07b84ec326fc674c5a295aa2908eb17715ceefd9f59d0)
BibTeX
@misc{dcd0d1becd83eb,
title = {Revisiting the directed pathwidth of h-semicomplete digraphs — arXiv:2610.41840},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.41840},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d0d1becd83eb; sha256 0b5de4d4a71763d733e07b84ec326fc674c5a295aa2908eb17715ceefd9f59d0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41840. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A digraph is $h$-semicomplete if every vertex has at most $h$ non-neighbors. In semicomplete digraphs, $k$-triples are obstructions to bounded directed pathwidth with many algorithmic applications: Fradkin and Seymour [JCTB 2013] showed that a large triple contains a subdivision of every small digraph, and triples were used for irrelevant vertex arguments in routing problems by Fomin and Pilipczuk [JCTB 2019] and Gomes, Lopes, and Sau [ICALP 2025]. Fradkin and Seymour also showed that there is a function $f(k)$ such that every semicomplete digraph of directed pathwidth at least $f(k)$ contains a $k$-triple, and their proof gives $f(k)$ triply exponential in $k$. For $h$-semicomplete digraphs, a result of Kitsunai et al. [ESA 2015] also yields a $k$-triple, but only existentially, and finding one in fixed-parameter time remained open. We improve the bound on $f(k)$ to a single exponential and extend the result to $h$-semicomplete digraphs: we show that every $h$-semicomplete digraph of directed pathwidth greater than $(h+1) \cdot k \cdot 2^{27k+9}$ contains a $k$-triple, which we find in polynomial time, and no bound subexponential in $k$ or sublinear in $h$ is possible. We also extend the approximation algorithm for directed pathwidth of Fomin and Pilipczuk to $h$-semicomplete digraphs, so its certificates of large directed pathwidth remain valid. Our proof is much shorter than the analysis of Kitsunai et al., and while their algorithm is exact, ours runs in polynomial time. As an application, we show that Arc-Disjoint Paths on $h$-semicomplete digraphs is fixed-parameter tractable parameterized by the number of paths and $h$, generalizing the semicomplete case. Finally, unlike in semicomplete digraphs, directed pathwidth does not bound directed cliquewidth: for every $k$, some acyclic $1$-semicomplete digraph, so of directed pathwidth zero, has directed cliquewidth at least $k$.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.41840 — 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-03T08:05:23.787Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).