A digraph is called $h$‑semicomplete if each vertex has at most $h$ non‑neighbors. In semicomplete digraphs, $k$‑triples serve as obstructions to bounded directed pathwidth and have many algorithmic uses. Fradkin and Seymour (JCTB 2013) showed that a sufficiently large directed pathwidth forces a $k$‑triple, with their bound $f(k)$ growing triple‑exponentially. Later, Kitsunai et al. (ESA 2015) extended this to $h$‑semicomplete digraphs but only proved existence, leaving a fixed‑parameter algorithm open. We improve the bound to a single exponential and generalize it: any $h$‑semicomplete digraph whose directed pathwidth exceeds $(h+1)\cdot k\cdot 2^{27k+9}$ contains a $k$‑triple, which can be found in polynomial time. Moreover, no sub‑exponential bound in $k$ or sub‑linear bound in $h$ is possible. We also adapt the approximation algorithm for directed pathwidth by Fomin and Pilipczuk to $h$‑semicomplete digraphs, preserving its large‑width certificates. Compared with the lengthy analysis of Kitsunai et al., our proof is much shorter; their algorithm is exact, while ours runs in polynomial time. As an application, we prove that the Arc‑Disjoint Paths problem on $h$‑semicomplete digraphs is fixed‑parameter tractable when parameterized by the number of paths and $h$, generalizing the semicomplete case. Finally, unlike the semicomplete setting, directed pathwidth does not bound directed cliquewidth: for every $k$ there exists an acyclic $1$‑semicomplete digraph (directed pathwidth zero) whose directed cliquewidth is at least $k$.
Review