Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld
Directed Pathwidth of Sequence Digraphs (extended abstract)
COCOA 2018 (LNCS 11346, pp. 79-93)
Abstract
| 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 Sk,l as the set of all digraphs G = (V, A) which can be defined by k sequences with at most l entries from V, such that (u, v) ∈ 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 O(k · (1+N)k), where N denotes the maximum sequence length. This leads to an XP-algorithm w.r.t. parameter 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. |
| Key words: directed path-width, transitive tournament, semicomplete digraph, XP-algorithm |