Computing Digraph Width Measures on Directed Co-graphs

Abstract

In this paper we consider the digraph width measures directed feedback vertex set number, cycle rank, DAG-depth, DAG-width and Kelly-width. While the minimization problem for these width measures is generally NP-hard, we prove that it is computable in linear time for all these parameters, except for Kelly-width, when restricted to directed co-graphs. As an important combinatorial tool, we show how these measures can be computed for the disjoint union, series composition, and order composition of two directed graphs, which further leads to some similarities and a good comparison between the width measures. This generalizes and expands our former results for computing directed path-width and directed tree-width of directed co-graphs.

The paper is eligible for the best student paper award.

C. Rehs—The work of the third author was supported by the German Research Association (DFG) grant GU 970/7-1.

1 Introduction

Undirected width parameters are well-known and frequently used in computations. Many NP-hard graph problems admit polynomial-time solutions when restricted to graphs of bounded width, like for example bounded tree-width or bounded path-width. Computing both parameters is hard even for bipartite graphs and complements of bipartite graphs [2], while for co-graphs it has been shown [7] that the path-width equals the tree-width and how to compute this value in linear time.

During the last years, width parameters for directed graphs have received a lot of attention [18]. Among these are directed tree-width and directed path-width. In our paper [21] we proved that for directed co-graphs both parameters are equal and computable in linear time. But directed tree-width and directed path-width are not the only attempts to generalize undirected tree-width and path-width for directed graphs. Furthermore, there are the parameters directed feedback vertex set number, cycle rank, DAG-depth, DAG-width and Kelly-width, which have also been considered in [17]. In this paper, we extend our results from [21] and give linear time solutions to compute these width parameters for the disjoint union, series composition and, except for Kelly-width, as well for the order composition of two directed graphs. This leads to a constructive linear-time-algorithm to get the width and the according decompositions of directed co-graphs. For most of the parameters, we could even expand this algorithm to extended directed co-graphs, which are an extension of the directed co-graphs defined in [12] by an additional operation considered in [24].

Our algorithms lead to some tightened bounds for directed path-width, directed tree-width, directed feedback vertex set number, cycle rank, DAG-depth, DAG-width and Kelly-width of extended directed co-graphs and for some of the parameters, they even lead to equalities.

2 Preliminaries

We use the notations of Bang-Jensen and Gutin [3] for graphs and digraphs. When talking about digraphs, we always mean directed graphs with neither multi-edges nor loops. A digraph is a tournament if for all vertices $u \ne v$, there is exactly one of the edges (u, v) and (v, u). It is completely bidirectional if both of these edges are in the edge set.

Orientations. An orientation of an undirected graph G is a digraph, where all edges $\{u,v\}$ of G are replaced by either (u, v) or (v, u). For a biorientation, every edge $\{u,v\}$ is replaced by either (u, v) or (v, u) or both. For a complete biorientation, every edge $\{u,v\}$ is replaced by (u, v) and (v, u). The complete biorientation of an undirected graph G is denoted by $\overleftrightarrow {G}$.

Special Directed Graphs. We recall some special directed graphs. Let

$$\overleftrightarrow {K_n}=(\{v_1,\ldots ,v_n\},\{ (v_i,v_j)~|~1\le i\ne j\le n\})$$

be a bidirectional complete digraph on n vertices. For $n \ge 2$ we denote by

$$\overrightarrow{P_n}=(\{v_1,\ldots ,v_n\},\{ (v_1,v_2),\ldots , (v_{n-1},v_n)\})$$

a directed path on n vertices and for $n \ge 2$ we denote by

$$\overrightarrow{C_n}=(\{v_1,\ldots ,v_n\},\{(v_1,v_2),\ldots , (v_{n-1},v_n),(v_n,v_1)\})$$

a directed cycle on n vertices. A directed acyclic digraph (DAG for short) is a digraph without any $\overrightarrow{C_n}$, $n\ge 2$ as subdigraph. By $\overrightarrow{T_n}$ we denote the transitive tournament on n vertices.

2.1 Recursively Defined Digraphs

Co-graphs have been introduced in the 1970s by a number of authors under different notations. We recall the definition of directed co-graphs from [12]. The following operations have already been considered by Bechet in [4].

• The disjoint union of $G_1, \ldots , G_k$, denoted by $G_1 \oplus \ldots \oplus G_k$, is the digraph with vertex set $V_1\cup \ldots \cup V_k$ and arc set $E_1\cup \ldots \cup E_k$.

• The series composition of $G_1,\ldots , G_k$, denoted by $G_1\otimes \ldots \otimes G_k$, is defined by their disjoint union plus all possible arcs between vertices of $G_i$ and $G_j$ for all $1\le i,j\le k$, $i\ne j$.

• The order composition of $G_1, \ldots , G_k$, denoted by $G_1\oslash \ldots \oslash G_k$, is defined by their disjoint union plus all possible arcs from vertices of $G_i$ to vertices of $G_j$ for all $1\le i < j\le k$.

The class of directed co-graphs can be defined recursively. The one-vertex-digraph is a directed co-graph and every disjoint union, series composition and order composition of directed co-graphs is a directed co-graph.

The following transformation has been considered by Johnson et al. in [24] and generalizes the operations disjoint union and order composition.

• The directed union of $G_1, \ldots , G_k$, denoted by $G_1\ominus \ldots \ominus G_k$, is a subdigraph of the order composition $G_1\oslash \ldots \oslash G_k$ and contains the disjoint union $G_1\oplus \ldots \oplus G_k$ as a subdigraph.

Including this operation to the definition of directed co-graphs, we obtain the class of extended directed co-graphs.

For every (extended) directed co-graph, we can define a tree structure, denoted as di-co-tree. The leaves of the di-co-tree represent the vertices of the digraph and the inner nodes of the di-co-tree correspond to the operations applied on the subexpressions defined by the subtrees. For every directed co-graph one can construct a di-co-tree in linear time, see [12].

Table 1. The value of digraph width measures of special digraphs.

3 Digraph Width Measures

In Table 1 we summarize some examples for the value of digraph width measures of special digraphs. Further examples can be found in [17, Table 1].

3.1 Directed Tree-Width

We will use the directed tree-width introduced by Johnson et al. [24].¹

An out-tree is a tree with a distinguished root such that all arcs are directed away from the root. For two vertices u, v of an out-tree T, the notation $u\le v$ means that there is a directed path on $\ge 0$ arcs from u to v and $u < v$ means that there is a directed path on $\ge 1$ arcs from u to v.

Let $G=(V,E)$ be some digraph and $Z\subseteq V$. A vertex set $S\subseteq V-Z$ is Z-normal if there is no directed path in $G-Z$ with first and last vertices in S that uses a vertex of $G-(Z\cup S)$.

Definition 1

(Directed tree-width, [24]). A (arboreal) tree-decomposition of a digraph $G=(V_G,E_G)$ is a triple $(T, \mathcal {X}, \mathcal {W})$. Here $T=(V_T,E_T)$ is an out-tree, $\mathcal {X}=\{X_e ~|~ e\in E_T\}$ and $\mathcal {W}=\{W_r~|~ r \in V_T\}$ are sets of subsets of $V_G$, such that the following two conditions hold true.

• (dtw-1) $\mathcal {W}=\{W_r~|~ r \in V_T\}$ is a partition of $V_G$ into non-empty subsets.²

• (dtw-2) For every $(u,v)\in E_T$ the set $\bigcup \{W_r ~|~ r\in V_T, v\le r\}$ is $X_{(u,v)}$-normal.

The width of a (arboreal) tree-decomposition $(T, \mathcal {X}, \mathcal {W})$ is

$$\max _{r\in V_T} |W_r\cup \bigcup _{e \sim r} X_e|-1.$$

Here, $e \sim r$ means that r is one of the two vertices of arc e. The directed tree-width of G, $\text {d-tw}(G)$ for short, is the smallest integer k such that there is a (arboreal) tree-decomposition $(T, \mathcal {X}, \mathcal {W})$ for G of width k.

Determining whether the directed tree-width of some given digraph is at most some given value w is NP-complete. On the other hand, determining whether the directed tree-width of some given digraph is at most some given value w is polynomial for directed co-graphs [21].

The results of [24] lead to an XP-algorithm³ for directed tree-width w.r.t. the standard parameter which implies that for each constant w, it is decidable in polynomial time whether a given digraph has directed tree-width at most w.

Lemma 1

([20, 21]). Let $G=(V_G,E_G)$ and $H=(V_H,E_H)$ be two vertex-disjoint digraphs, then the following properties hold.

• 1. $\text {d-tw}(G\oplus H)=\max \{\text {d-tw}(G),\text {d-tw}(H)\}$

• 2. $\text {d-tw}(G\oslash H)=\max \{\text {d-tw}(G),\text {d-tw}(H)\}$

• 3. $\text {d-tw}(G\ominus H)=\max \{\text {d-tw}(G),\text {d-tw}(H)\}$

• 4. $\text {d-tw}(G\otimes H)=\min \{\text {d-tw}(G)+|V_H|,\text {d-tw}(H)+|V_G|\}$

3.2 Directed Path-Width

The notation of directed path-width was introduced by Reed, Seymour, and Thomas around 1995 and relates to directed tree-width introduced by Johnson, Robertson, Seymour, and Thomas in [24].

Definition 2

(Directed path-width). A directed path-decomposition of some digraph $G=(V,E)$ is a sequence $(X_1, \ldots , X_r)$ of subsets of V, called bags, such that the following three conditions hold true.

• (dpw-1) $X_1 \cup \ldots \cup X_r ~=~ V$.

• (dpw-2) For each $(u,v) \in E$ there is a pair $i \le j$ such that $u \in X_i$ and $v \in X_j$.

• (dpw-3) If $u \in X_i$ and $u \in X_j$ for some $u\in V$ and two indices i, j with $i \le j$, then $u \in X_\ell$ for all indices $\ell$ with $i \le \ell \le j$.

The width of a directed path-decomposition $\mathcal{X}=(X_1, \ldots , X_r)$ is

$$\max _{1 \le i \le r} |X_i|-1.$$

The directed path-width of G, $\text {d-pw}(G)$ for short, is the smallest integer w such that there is a directed path-decomposition of G of width w.

Determining whether the directed path-width of some given digraph with maximum semi-degree $\Delta ^0(G)=\max \{\Delta ^-(D),\Delta ^+(D)\}\le 3$ is at most some given value w is NP-complete by a reduction from undirected path-width for planar graphs with maximum vertex degree 3 [26].

Lemma 2

([20, 21]). Let $G=(V_G,E_G)$ and $H=(V_H,E_H)$ be two vertex-disjoint digraphs, then the following properties hold.

• 1. $\text {d-pw}(G\oplus H)=\max \{\text {d-pw}(G),\text {d-pw}(H)\}$

• 1. $\text {d-pw}(G\oslash H)=\max \{\text {d-pw}(G),\text {d-pw}(H)\}$

• 1. $\text {d-pw}(G\ominus H)=\max \{\text {d-pw}(G),\text {d-pw}(H)\}$

• 1. $\text {d-pw}(G\otimes H)=\min \{\text {d-pw}(G)+|V_H|,\text {d-pw}(H)+|V_G|\}$

3.3 Directed Feedback Vertex Set (DFVS) Number

Definition 3

(DFVS-number). The directed feedback vertex set number of a digraph $G=(V,E)$, denoted by $\text {dfn}(G)$, is the minimum cardinality of a set $S\subset V$ such that $G-S$ is a DAG.

Theorem 1

($\bigstar$⁴). Let $G=(V_G,E_G)$ and $H=(V_H,E_H)$ be two vertex-disjoint digraphs, then the following properties hold.

• 1. $\text {dfn}(G\oplus H)=\text {dfn}(G)+\text {dfn}(H)$

• 2. $\text {dfn}(G\oslash H)=\text {dfn}(G)+\text {dfn}(H)$

• 3. $\text {dfn}(G\ominus H)=\text {dfn}(G)+\text {dfn}(H)$

• 4. $\text {dfn}(G\otimes H)=\min \{\text {dfn}(G)+|V_H|,\text {dfn}(H)+|V_G|\}$

3.4 Cycle Rank

Cycle rank was introduced in [15] and also appeared in [8] and [25].

Definition 4

(Cycle rank). The cycle rank of a digraph $G=(V,E)$, denoted by $\text {cr}(G)$, is defined as follows.

• If G is acyclic, $\text {cr}(G)=0$.

• If G is strongly connected, then $\text {cr}(G)=1+\min _{v\in V} \text {cr}(G-\{v\})$.

• Otherwise the cycle rank of G is the maximum cycle rank of any strongly connected component of G.

Results on the cycle rank can be found in [19]. In this papers Gruber proved the hardness of computing cycle rank, even for sparse digraphs of maximum outdegree at most 2.

Proposition 1

([19]). For every digraph G, we have $\text {d-pw}(G)\le \text {cr}(G)$.

The cycle rank can be much larger than the directed path-width, which can be shown by a complete biorientation of a path graph $\overleftrightarrow {P_n}$ which has directed path-width 1 but arbitrary large cycle rank $\lfloor \log (n)\rfloor$, see [25].

Proposition 2

([17]). For every digraph G, we have $\text {cr}(G)\le \text {dfn}(G)$.

The DFVS-number can be much larger than the cycle rank, which can be shown by the disjoint union of $\frac{n}{3}$ directed cycles $\overrightarrow{C_3}$ which has cycle rank 1 but arbitrary large DFVS-number $\frac{n}{3}$.

Theorem 2

($\bigstar$ ). Let $G=(V_G,E_G)$ and $H=(V_H,E_H)$ be two vertex-disjoint digraphs, then the following properties hold.

• 1. $\text {cr}(G\oplus H)=\max \{\text {cr}(G),\text {cr}(H)\}$

• 2. $\text {cr}(G\oslash H)=\max \{\text {cr}(G),\text {cr}(H)\}$

• 3. $\text {cr}(G\ominus H)=\max \{\text {cr}(G),\text {cr}(H)\}$

• 4. $\text {cr}(G\otimes H)=\min \{\text {cr}(G)+|V_H|,\text {cr}(H)+|V_G|\}$

3.5 DAG-depth

The DAG-depth of a digraph was introduced in [16] motivated by tree-depth for undirected graphs, given in [27].

For a digraph $G=(V,E)$ and $v\in V$, let $G_v$ denote the subdigraph of G induced by the vertices which are reachable from v. The maximal elements in the partially ordered set $\{G_v~|~v\in V\}$ w.r.t. the graph inclusion order are the reachable fragments of G and will be denoted by R(G).⁵

Definition 5

(DAG-depth). Let $G=(V,E)$ be a digraph. The DAG-depth of G, denoted by $\text {ddp}(G)$, is defined as follows.

• If $|V|=1$, then $\text {ddp}(G)=1$.

• If G has a single reachable fragment, then $\text {ddp}(G)=1+\min \{\text {ddp}(G-v)~|~v\in V\}$.

• Otherwise, $\text {ddp}(G)$ equals the maximum over the DAG-depth of the reachable fragments of G.

Proposition 3

([17]). For every complete bioriented directed G, we have $\text {ddp}(G)=\text {cr}(G)+1$.

Theorem 3

Let $G=(V_G,E_G)$ and $H=(V_H,E_H)$ be two vertex-disjoint digraphs, then the following properties hold.

• 1. $\text {ddp}(G\oplus H)=\max \{\text {ddp}(G),\text {ddp}(H)\}$

• 2. $\text {ddp}(G\oslash H)=\text {ddp}(G)+\text {ddp}(H)$

• 3. $\text {ddp}(G\ominus H)\le \text {ddp}(G)+\text {ddp}(H)$

• 4. $\text {ddp}(G\otimes H)=\min \{\text {ddp}(G)+|V_H|,\text {ddp}(H)+|V_G|\}$

Proof

• 1. Since there is no edge in $G\oplus H$ between a vertex from $V_G$ and a vertex from $V_H$, every reachable fragment is a subset of $V_G$ or a subset of $V_H$.

• 2. First, we observe that the set of reachable fragments for $G\oslash H$ can be obtained by $R(G\oslash H)=\{f\cup V_H\mid f\in R(G)\}$.

  $\text {ddp}(G\oslash H)\le \text {ddp}(G)+\text {ddp}(H)$

  First, we remove the vertices of G from $G\oslash H$ in the same order as from G when verifying the depth of $\text {ddp}(G)$ using Definition 5. Afterwards, we remove the vertices of H from $G\oslash H$ in the same order as from H when verifying the depth of $\text {ddp}(H)$ using Definition 5. The observation above allows to use this ordering.

  $\text {ddp}(G\oslash H)\ge \text {ddp}(G)+\text {ddp}(H)$

  First suppose that it is optimal to begin removing vertices from $V_G$ of $G\oslash H$. Then it is no drawback to remove all vertices from $V_G$ of $G\oslash H$ first and all vertices from $V_H$ afterwards, since every vertex of $V_H$ is reachable from every vertex of $V_G$. Since none of the vertices of $V_G$ is reachable from a vertex of $V_H$ the vertices of $V_H$ do not effect the number of fragments, reachable from $V_G$. Next, suppose that it is optimal to begin removing vertices from $V_H$ of $G\oslash H$. Then it is no drawback to remove all vertices from $V_H$ of $G\oslash H$ first and all vertices from $V_G$ afterwards, since none of the vertices of $V_G$ is reachable from a vertex of $V_H$ and thus the vertices of $V_G$ do not effect the number of fragments, reachable from $V_H$.

• 3. $\text {ddp}(G\ominus H)\le \text {ddp}(G)+\text {ddp}(H)$ holds, since the equality of 2. does not hold true in this case, since for a small number of edges $\text {ddp}(G\ominus H)$ is much smaller than $\text {ddp}(G)+\text {ddp}(H)$. Note that a lower bound is $\text {ddp}(G\ominus H)\ge \max \{\text {ddp}(G),\text {ddp}(H)\}$, since $G\ominus H$ is equal to the disjoint union if no edges emerge.

• 4. $\text {ddp}(G\otimes H)\le \min \{\text {ddp}(G)+|V_H|,\text {ddp}(H)+|V_G|\}$

  Since $G\otimes H$ has only one reachable fragment as long as it contains vertices from $V_G$ and vertices from $V_H$, we can apply the second case of Definition 5 to verify an upper bound of $\text {ddp}(G)+|V_H|$ by removing the vertices of H one by one from $G\otimes H$ and to verify an upper bound of $\text {ddp}(H)+|V_G|$ by removing the vertices of G one by one from $G\otimes H$.

  $\text {ddp}(G\otimes H)\ge \min \{\text {ddp}(G)+|V_H|,\text {ddp}(H)+|V_G|\}$

  Since in $G\otimes H$ every vertex of $V_G$ has an edge to and from every vertex of $V_H$, $G\otimes H$ has only one reachable fragment as long as it contains vertices from $V_G$ and $V_H$. Thus, we have to apply the second case of Definition 5 as long we have vertices from $V_G$ and vertices from $V_H$. This either leads to a subdigraph induced by $V_G-V'_G$ for some $V'_G\subset V_G$ or to a subdigraph induced by $V_H-V'_H$ for some $V'_H\subset V_H$. Thus, we have

  $$ \begin{array}{lcl} \text {ddp}(G\otimes H) &{}\ge &{}\min \{|V_H|+|V'_G|+\text {ddp}(G-V'_G), \\ &{}&{}~~~~~~~|V_G|+|V'_H|+\text {ddp}(H-V'_H)\}\\ &{} \ge &{} \min \{|V_H|+\text {ddp}(G),|V_G|+\text {ddp}(H)\}. \end{array} $$

This completes the proof.    $\square$

Note that $\text {ddp}(G\ominus H)$ cannot be computed from $\text {ddp}(G)$ and $\text {ddp}(H)$ by a simple formula, since the disjoint union and the order operation behave differently.

3.6 DAG-width

The DAG-width is a graph parameter which describes how close a digraph is to a directed acyclic graph (DAG). It has been defined in [5, 6, 28].

Let $G=(V_G,E_G)$ be a acyclic digraph. The partial order $\preccurlyeq _G$ on G is the reflexive, transitive closure of $E_G$. A source or root of a set $X \subseteq V_G$ is a $\preccurlyeq _G$-minimal element of X, that is, $r \in X$ is a root of X, if there is no $y \in X$, such that $y \preccurlyeq _G r$ and $y \ne x$. Analogously, a sink or leaf of a set $X \subseteq V_G$ is a $\preccurlyeq _G$-maximal element.

Let $V' \subseteq V_G$, then a set $W \subseteq V_G$ guards $V'$ if for all $(u,v) \in E_G$ it holds that if $u \in V'$ then $v \in V' \cup W$.

Definition 6

(DAG-width). A DAG-decomposition of some digraph $G=(V_G,E_G)$ is a pair $(D, \mathcal {X})$ where $D=(V_D, E_D)$ is a DAG and $\mathcal {X} = \{X_u \mid X_u \subseteq V_G, u \in V_D\}$ is a family of subsets of $V_G$ such that:

• (dagw-1) $\bigcup _{u \in V_D} X_u = V_G$.

• (dagw-2) For all vertices $u,v,w \in V_D$ with $u \succcurlyeq _D v \succcurlyeq _D w$, it holds that $X_u \cap X_w \subseteq X_v$.

• (dagw-3) For all edges $(u,v) \in E_D$ it holds that $X_u \cap X_v$ guards $X_{\succcurlyeq _v} \setminus X_u$, where $X_{\succcurlyeq _v} = \cup _{v \succcurlyeq _D w } X_w$. For any source u, $X_{\succcurlyeq _u}$ is guarded by $\emptyset$.

The width of a DAG-decomposition $(D,\mathcal {X})$ is the number

$$\max _{u\in V_D} |X_u|.$$

The DAG-width of a digraph G, $\text {dagw}(G)$ for short, is the smallest width of all possible DAG-decompositions for G.

We use the restriction to nice DAG-decompositions from [6, Theorem 24].

Proposition 4

([6]). For every graph G, we have $\text {dagw}(\overleftrightarrow {G}) = \text {tw}(G)+1$.

Proposition 4 implies that the NP-hardness of tree-width carries over to DAG-width.

There are even digraphs on n vertices whose optimal DAG-decompositions have super-polynomial many bags w.r.t n [1]. Furthermore, it has been shown that deciding whether the DAG-width of a given digraph is at most a given value is PSPACE-complete [1].

Proposition 5

([17]). For every digraph G, we have $\text {dagw}(G)\le \text {d-pw}(G)+1$.

Proposition 6

([6]). For every digraph G, we have $\text {d-tw}(G)\le 3\cdot \text {dagw}(G)+1$.

Lemma 3

($\bigstar$). Let $G=(V,E)$ be a digraph of DAG-width at most k, such that $V_1\cup V_2=V$, $V_1\cap V_2=\emptyset$, and $\{(u,v),(v,u)~|~u\in V_1, v\in V_2\}\subseteq E$. Then there is a DAG-decomposition $(D, \mathcal {X})$, $D=(V_D,E_D)$, of width at most k for G such that for every $v\in V_D$ holds $V_1\subseteq X_v$ or for every $v\in V_D$ holds $V_2\subseteq X_v$.

Obviously, this lemma also holds for a nice DAG-decomposition.

Theorem 4

Let $G=(V_G,E_G)$ and $H=(V_H,E_H)$ be two vertex-disjoint digraphs, then the following properties hold.

• 1. $\text {dagw}(G\oplus H)=\max \{\text {dagw}(G),\text {dagw}(H)\}$

• 2. $\text {dagw}(G\oslash H)=\max \{\text {dagw}(G),\text {dagw}(H)\}$

• 3. $\text {dagw}(G\ominus H)=\max \{\text {dagw}(G),\text {dagw}(H)\}$

• 4. $\text {dagw}(G\otimes H)=\min \{\text {dagw}(G)+|V_H|,\text {dagw}(H)+|V_G|\}$

Proof

Let G and H be two vertex-disjoint digraphs and let further $(D_G,\mathcal {X}_G)$ and $(D_H, \mathcal {X}_H)$ be their nice DAG-decompositions with minimum DAG-width. Let $r_H$ be the root of $D_H$ and let $l_G$ be a leaf of $D_G$.

• 1. For $J = G \oplus H$, we first define a legit DAG-decomposition $(D_J,\mathcal {X}_J)$ for J and show that it is of minimum width afterwards. Let $D_J$ be the disjoint union of $D_G$ and $D_H$ with an additional arc $(l_G,r_H)$. Further, $\mathcal {X}_J=\mathcal {X}_G \cup \mathcal {X}_H$. $(D_J,\mathcal {X}_J)$ is a valid DAG-decomposition because it satisfies the conditions as follows. It holds that (dagw-1) is satisfied by $(D_G,\mathcal {X}_G)$ and $(D_H, \mathcal {X}_H)$ it is also satisfied by $(D_J,\mathcal {X}_J)$ because all vertices of J are included. As we do not add any vertices to the X-sets and G and H are vertex-disjoint, (dagw-2) is satisfied for $(D_J, \mathcal {X}_J)$. Further, (dagw-3) is satisfied for all arcs in $D_G$ and $D_H$. In $D_J$ there is only one additional arc, $(l_G,r_H)$. Since it holds that for $r_H$, $X_{\succcurlyeq r_H}$ is guarded by $\emptyset$ and we do not add any outgoing vertices to H and $X_{l_G} \cap X_{r_H} = \emptyset$, (dagw-3) is satisfied for $(D_J, \mathcal {X}_J)$. Thus, the DAG-width of the decomposition is limited by the larger width of G and H, such that $\text {dagw}(G\oplus H)\le \max \{\text {dagw}(G),\text {dagw}(H)\}$.

  The lower bound holds as G and H are both induced subdigraphs of J and a graph cannot have lower DAG-width than its induced subdigraphs. Hence $\text {dagw}(J)\ge \max \{\text {dagw}(G),\text {dagw}(H)\}$ applies, which leads to $\text {dagw}(J)=\max \{\text {dagw}(G),\text {dagw}(H)\}$.

• 2. Holds by the same arguments as given in (1.).

• 3. Holds by the same arguments as given in (1.).

• 4. For $J=G\otimes H$, set $D_J = D_G$ and $\mathcal {X}_J =\{X_u \cup V_H \mid X_u \in \mathcal {X}_G\}$. Then $(D_J, \mathcal {X}_J)$ is a DAG-decomposition for J: Obviously, (dagw-1) is satisfied. (dagw-2) and (dagw-3) are satisfied since they are satisfied for $\mathcal {X}_G$ and we add $V_H$ to every vertex set in $\mathcal {X}_G$. Further, it holds that the width of $(D_J, \mathcal {X}_J)$ is $\text {dagw}(G)+|V_H|$. In the same way, we get a DAG-decomposition of width $\text {dagw}(H)+|V_G|$, so we have $\text {dagw}(G\otimes H)\le \min \{\text {dagw}(G)+|V_H|,\text {dagw}(H)+|V_G|\}$.

  For the lower bound, we use Lemma 3. Assume that $\text {dagw}(G\otimes H)<\min \{\text {dagw}(G)+|V_H|,\text {dagw}(H)+|V_G|\}$. Let $(D_J, \mathcal {X}_J)$ be a minimal DAG-decomposition of J of size $k < \min \{\text {dagw}(G)+|V_H|,\text {dagw}(H)+|V_G|\}$. By Lemma 3 we have $V_H \subseteq X_v$ for all $X_v \in \mathcal {X}_J$ or $V_G \subseteq X_v$ for all $X_v \in \mathcal {X}_J$. Without loss of generality assume $V_H \subseteq X_v$ for all $X_v \in \mathcal {X}_J$ (because $V_G \subseteq X_v$ for all $X_v \in \mathcal {X}_J$, respectively). Then $(D'_G, \mathcal {X}'_G)$ with $D'_G=D_J$, $\mathcal {X}'_G = \{ X_u \setminus V_H \mid X_u \in \mathcal {X}_J \}$ is a DAG-decomposition of size $k-|V_H|$ of G:

  • (dagw-1) is satisfied since

    $$\begin{array}{lcl} \bigcup _{u \in V_{D'_G}} X_u &{}=&{} \bigcup _{u \in V_{D_J}} (X_u \setminus V_H) = \left( \bigcup _{u \in V_{D_J}} X_u \right) \setminus V_H \\ &{}=&{}V_J \setminus V_H \\ &{}=&{} \left( V_G \cup V_H\right) \setminus V_H \\ &{}=&{} V_G. \end{array} $$

  • (dagw-2) is satisfied since for all $u,v,w \in V_{D'_G}$ with $u \succcurlyeq _{D'_G} v \succcurlyeq _{D'_G} w$ and $X_u^J, X_v^J$ and $X_w^J$ the corresponding sets in $(D_J, \mathcal {X}_J)$ it holds that $X_u \cap X_w = \left( X_u^J \setminus V_H \right) \cap \left( X_w^J \setminus V_H \right) = \left( X_u^J \cap X_w^J \right) \setminus V_H \subseteq X_v^J \setminus V_H = X_v$ as $u \succcurlyeq _{D_J} v \succcurlyeq _{D_J} w$.

  • (dagw-3) is satisfied since for all edges $(u,v) \in E_{D'_G}$, we have $(u,v) \in E_{D_J}$ and as $X_u \cap X_v = \left( X_u^J \cap X_v^J \right) \setminus V_H$ which guards $X_{\succcurlyeq _{D'_G} v} \setminus X_u = X_{\succcurlyeq _{D_J} v} \setminus X^J_u$. For the root, the condition is trivially satisfied.

  But it holds that $k-|V_H| < \min \{\text {dagw}(G)+|V_H|,\text {dagw}(H)+|V_G|\} - |V_H| \le \text {dagw}(G)+|V_H| -|V_H| = \text {dagw}(G)$. This is a contradiction, as it is not possible to create a DAG-decomposition of size smaller than $\text {dagw}(G)$. It follows that $\text {dagw}(G\otimes H)\ge \min \{\text {dagw}(G)+|V_H|,\text {dagw}(H)+|V_G|\}$ and thus that $\text {dagw}(G\otimes H)=\min \{\text {dagw}(G)+|V_H|,\text {dagw}(H)+|V_G|\}$.

This completes the proof.   $\square$

3.7 Kelly-Width

The Kelly-width is also led from directed acyclic graphs, which leads to the idea that it is very similar to the DAG-width. It has been defined in [22].

Definition 7

(Kelly-width). A Kelly decomposition of a digraph $G=(V_G,E_G)$ is a triple $( \mathcal {W}, \mathcal {X}, D)$ where D is a directed acyclic graph, $\mathcal {X} = \{X_u \mid X_u \subseteq V_G, u \in V_D\}$ and $\mathcal {W} = \{W_u \mid W_u \subseteq V_G, u \in V_D\}$ are families of subsets of $V_G$ such that:

• 1. $\mathcal {W}$ is a partition for $V_G$.

• 2. For all vertices $v \in V_G$, $X_v$ guards $W_{\succcurlyeq _v}$.

• 3. For all vertices $v \in V_G$, there is a linear order $u_1, \dots , u_s$ on the children of v such that for every $u_i$ it holds that $X_{u_i} \subseteq W_i \cup X_i \cup \bigcup _{j<i} W_{\succcurlyeq _{u_j}}$. Similarly,there is a linear order $r_1, r_2, \dots$ on the roots of D such that for each root $r_i$ it holds that $W_{r_i} \subseteq \bigcup _{j<i} W_{\succcurlyeq _{r_j}}$.

The width of a Kelly decomposition $(\mathcal {W}, \mathcal {X}, D)$ is the number

$$\max _{u\in V_D} |X_u|+|W_u|.$$

The Kelly-width of a digraph G, denoted with $\text {kw}(G)$, is the smallest width of all possible Kelly decompositions for G.

Definition 8

(Directed elimination ordering). Let $G=(V,E)$ be a digraph. A directed elimination ordering $\vartriangleleft$ on G is a linear ordering on V. For $\vartriangleleft = (v_0, v_1, \dots , v_{n-1})$ we define

• $G_0^{\vartriangleleft } = G$

• $G_{i+1}^{\vartriangleleft } = (V_{i+1}^{\vartriangleleft }, E_{i+1}^{\vartriangleleft })$ with $V_{i+1}^{\vartriangleleft } = V_i^{\vartriangleleft } \setminus \{v_i\}$ and

  $E_{i+1}^{\vartriangleleft } = \left\{ (u,v) \mid (u,v) \in E_i^{\vartriangleleft }\text { and } u,v \ne v_i \text { or } (u,v_i), (v_i, v) \in E_i^{\vartriangleleft }, u \ne v \right\}$

$G_i^{\vartriangleleft }$ is the directed elimination graph at step i according to $\vartriangleleft$.

The width of $\vartriangleleft$ is the maximum out-degree of $v_i$ in $G_i^{\vartriangleleft }$ over all i.

Lemma 4

([22]). Let G be a digraph. The following are equivalent:

• 1. G has Kelly-width at most $k+1$

• 2. G has a directed elimination ordering of width $\le ~k$

Proposition 7

([22]). For every digraph G, we have $\text {d-tw}(G)\le 6\cdot \text {kw}(G)-2$.

Proposition 8

([17]). For every digraph G, we have $\text {kw}(G)\le \text {d-pw}(G)+1$.

Theorem 5

Let $G=(V_G,E_G)$ and $H=(V_H,E_H)$ be two vertex-disjoint digraphs, then the following properties hold.

• 1. $\text {kw}(G\oplus H)=\max \{\text {kw}(G),\text {kw}(H)\}$

• 2. $\text {kw}(G\oslash H)=\max \{\text {kw}(G),\text {kw}(H)\}$

• 3. $\text {kw}(G\ominus H)= \max \{\text {kw}(G),\text {kw}(H)\}$

• 4. $\text {kw}(G\otimes H) \le \min \{\text {kw}(G)+|V_H|,\text {kw}(H)+|V_G|\}$

Proof

We use the fact that by Lemma 4, a digraph has Kelly-width $k+1$ if and only if it has a directed elimination ordering of width k. Let $G=(V_G, E_G)$ and $H=(V_H, E_H)$ be two vertex-disjoint digraphs with $\text {kw}(G)= k_G$ and $\text {kw}(H)=k_H$. Then, there exists a directed elimination ordering $\vartriangleleft _G$ of G of width $k_G -1$ and a directed elimination ordering $\vartriangleleft _H$ of H of width $k_H - 1$.

• 1. For $J = G \oplus H$, we obtain a linear ordering $\vartriangleleft _J$ of J by adding first all vertices from $\vartriangleleft _H$ and from $\vartriangleleft _G$ to $\vartriangleleft _J$ afterwards. As no edges from H to G are inserted to J, this is a directed elimination ordering of width $\max \{ k_H -1, k_G -1\}$. As G and H are both induced subdigraphs of J, there cannot exist a directed elimination ordering of smaller width. By Lemma 4 it follows that $\text {kw}(J) = \max \{k_H, k_G\}$, such that $\text {kw}(G\oplus H)=\max \{\text {kw}(G),\text {kw}(H)\}$.

• 2. Holds by the same arguments as in (1.).

• 3. Holds by the same arguments as in (1.).

• 4. For $J=G\otimes H$, we obtain a linear ordering $\vartriangleleft _J$ of J by adding first all vertices from $\vartriangleleft _H$ and afterwards from $\vartriangleleft _G$ to $\vartriangleleft _J$ (first $\vartriangleleft _G$, then $\vartriangleleft _H$ respectively). As there are exactly $V_G$ ($V_H$) more outgoing edges for every vertex in $V_H$ ($V_G$), this is a directed elimination ordering of J of width $k_H-1 +|V_G|$ ($k_G-1 +|V_H|$, respectively).

This completes the proof.   $\square$

Remark 1

($\bigstar$). The value $\min \{\text {kw}(G)+|V_H|,\text {kw}(H)+|V_G|\}$ is not a lower bound for $\text {kw}(G\otimes H)$, even not if G and H are directed co-graphs.

3.8 Comparison

Theorem 6

For every extended directed co-graph G, we have

$$\text {kw}(G) \le \text {d-pw}(G)=\text {d-tw}(G)=\text {cr}(G)=\text {dagw}(G)-1 \le \text {ddp}(G)-1 \le \text {dfn}(G).$$

For DFVS-Number, DAG-depth and Kelly-width equality is not possible by the following examples. For the disjoint union of two $\overleftrightarrow {K_n}$, it holds that $\text {d-pw}(2\overleftrightarrow {K_n}) = n-1 < 2n-2 = \text {dfn}(2\overleftrightarrow {K_n}).$ For transitive tournaments $\overrightarrow{T_n}$, it holds that $\text {d-pw}(\overrightarrow{T_n})= 0 < n =\text {ddp}(\overrightarrow{T_n})$. Further, let $K'_n$ be the 2n vertex graph which is obtained by a complete graph $K_n$ on n vertices and adding a pendant vertex for every of the n vertices of $K_n$, then for the complete biorientation $\overleftrightarrow {K'_n}$ it holds that $\text {kw}(\overleftrightarrow {K'_n}\otimes \overleftrightarrow {K'_n}) = 2n-1 < 3n-1 = \text {d-pw}(\overleftrightarrow {K'_n}\otimes \overleftrightarrow {K'_n})$.

But by Theorem 5 Kelly-width is always smaller or equal to path-width and its equal parameters and by Theorem 3 DAG-depth is always greater or equal to path-width and its equal parameters.

Theorem 7

For every extended directed co-graph $G=(V,E)$ which is given by a binary di-co-tree the directed path-width, directed tree-width, directed feedback vertex set number, cycle rank, and DAG-width can be computed in time $\mathcal {O}(|V|)$.

4 Conclusion and Outlook

In this paper, we are able to give linear time algorithms for the directed feedback set number, cycle rank and DAG-width of extended directed co-graphs and a linear-time algorithm for the DAG-depth of directed co-graphs. Further, we provided a comparison of all considered parameters for extended directed co-graphs and obtained equality for directed path-width, directed tree-width, cycle rank and DAG width. Further, we showed for bounds for the class of directed co-graphs for the directed vertex set number, DAG-depth and Kelly-width. This widely extends our results for directed path-width and directed tree-width from [21].

A further issue could be to find a linear or polynomial time algorithm to compute Kelly-width on directed co-graphs. Furthermore, it would be interesting for which superclasses of directed co-graphs it is still possible to find polynomial algorithms to get the considered parameters and for which superclasses these problems become NP-hard.