On the pathwidth of almost semicomplete digraphs

Kenta Kitsunai, Yasuaki Kobayashi, Hisao Tamaki

We call a digraph {\em $h$-semicomplete} if each vertex of the digraph has at most $h$ non-neighbors, where a non-neighbor of a vertex $v$ is a vertex $u\ne v$ such that there is…