Directed Path-Width of Sequence Digraphs

Computing the directed path-width of a digraph is NP-hard even for digraphs of maximum semi-degree 3. In this paper we consider a family of graph classes called sequence digraphs, such that for each of these classes the directed path-width can be computed in polynomial time. For this purpose we define the graph classes \(S_{k,\ell }\) as the set of all digraphs \(G=(V,A)\) which can be defined by k sequences with at most \(\ell \) entries from V, such that \((u,v) \in A\) if and only if in one of the sequences u occurs before v. We characterize digraphs which can be defined by \(k=1\) sequence by four forbidden subdigraphs and also as a subclass of semicomplete digraphs. Given a decomposition of a digraph G into k sequences, we show an algorithm which computes the directed path-width of G in time , where N denotes the maximum sequence length. This leads to an XP-algorithm w.r.t. k for the directed path-width problem. As most known parameterized algorithms for directed path-width consider the standard parameter, our algorithm improves significantly the known results for a high amount of digraphs of large directed path-width.