{"id":"arxiv/2610.41840","url":"https://arxiv.org/abs/2610.41840","tags":["math.CO","cs.DS"],"score":0,"title":"Revisiting the directed pathwidth of h-semicomplete digraphs","domain":"math.CO","source":"arxiv","authors":["Guilherme C. M. Gomes","Raul Lopes","Matthias Mnich"],"reviews":0,"subject":"math.CO","summary":"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)$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}