Revisiting the directed pathwidth of h-semicomplete digraphs

Guilherme C. M. Gomes, Raul Lopes, Matthias Mnich

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 algorith…