Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract)

Abstract

We consider the Directed Steiner Path Cover problem on directed co-graphs. Given a directed graph $G=(V(G),E(G))$ and a set $T \subseteq V(G)$ of so-called terminal vertices, the problem is to find a minimum number of directed vertex-disjoint paths, which contain all terminal vertices and a minimum number of non-terminal vertices (Steiner vertices). The primary minimization criteria is the number of paths. We show how to compute a minimum Steiner path cover for directed co-graphs in linear time. For $T = V(G)$, the algorithm computes a directed Hamiltonian path if such a path exists.

This work was funded in part by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 388221852.

1 Introduction

The Steiner path problem is a restriction of the Steiner tree problem such that the required terminal vertices lie on a path of minimum cost. The related Euclidean bottleneck Steiner path problem was considered in [1] and a linear time solution for the Steiner path problem on trees was given in [11].

While a Steiner tree always exists within connected graphs, it is not always possible to find a Steiner path, which motivates us to consider Steiner path cover problems. The Steiner connectivity problem was considered in [4].

In this article we consider the Directed Steiner Path Cover problem defined as follows. Let G be a directed graph on vertex set V(G) and edge set E(G) and let $T \subseteq V(G)$ be a set of terminal vertices. A directed Steiner path cover for G is a set of vertex-disjoint simple directed paths in G that contain all terminal vertices of T and possibly also some of the non-terminal (Steiner) vertices of $V(G) - T$. The size of a directed Steiner path cover is the number of its paths, the cost is defined as the minimum number of Steiner vertices in a directed Steiner path cover of minimum size.

• Name: Directed Steiner Path Cover

• Instance: A directed graph G and a set of terminal vertices $T \subseteq V(G)$.

• Task: Find a directed Steiner path cover of minimum cost for G.

The Directed Steiner Path Cover problem generalizes the directed Hamiltonian path problem, implying that it is NP-hard. This motivates us to restrict the problem to special inputs. We consider a very natural class of inputs, which is defined as follows.

Directed co-graphs (short for directed complement reducible graphs) can be generated from the single vertex graph by applying disjoint union, order composition and series composition [3]. They also can be characterized by excluding eight forbidden induced subdigraphs, see [6, Fig. 2]. Directed co-graphs are exactly the digraphs of directed NLC-width 1 and a proper subset of the digraphs of directed clique-width at most 2 [9]. Directed co-graphs are also interesting from an algorithmic point of view since several hard graph problems can be solved in polynomial time by dynamic programming along the tree structure of the input graph, see [2, 7, 8]. Moreover, directed co-graphs are very useful for the reconstruction of the evolutionary history of genes or species using genomic sequence data [12].

In this paper we show how the value of a Steiner path cover of minimum size and cost for the disjoint union, order and series composition of two digraphs can be computed in linear time from the corresponding values of the involved digraphs. Therefore, we define a useful normal form for directed Steiner path covers in digraphs which are defined by the order composition or series composition of two digraphs. Further we sketch an algorithm which constructs a directed Steiner path cover of minimum size and cost for a directed co-graph in linear time.

2 Preliminaries

Definition 1

([3]). The class of directed co-graphs is recursively defined as follows.

• (i) Every digraph on a single vertex $(\{v\},\emptyset )$, denoted by $\bullet _v$, is a directed co-graph.

• (ii) If A, B are vertex-disjoint directed co-graphs, then

  • (a) the disjoint union $A \oplus B$, which is defined as the digraph with vertex set $V(A) \cup V(B)$ and edge set $E(A) \cup E(B)$,

  • (b) the order composition $A \oslash B$, defined by their disjoint union plus all possible edges from V(A) to V(B), and

  • (c) the series composition $A \otimes B$, defined by their disjoint union plus all possible edges between V(A) and V(B), are directed co-graphs.

The recursive generation of a co-graph can be described by a tree called directed co-tree. The leaves of the directed co-tree represent the vertices of the digraph and the inner vertices of the directed co-tree correspond to the operations applied on the subgraphs of G defined by the subtrees. For every directed co-graph one can construct a directed co-tree in linear time, see [6].

Next we define a normal form for directed Steiner path covers in digraphs. Therefore we introduce some notations. Let G be a directed co-graph, let $T \subseteq V(G)$ be a set of terminal vertices, and let C be a directed Steiner path cover for G with respect to T. Then, $\mathfrak {s}(C)$ denotes the number of Steiner vertices in the paths of C. We define p(G, T) as the minimum number of paths within a Steiner path cover for G with respect to T. Further let s(G, T) be the minimum number of Steiner vertices in a directed Steiner path cover of size p(G, T) with respect to T. We do not specify set T if it is clear from the context which set is meant.

Lemma 1

Let C be a directed Steiner path cover for some directed co-graph $G = A \otimes B$ or $G = A \oslash B$ with respect to a set T of terminal vertices. Then, there is a directed Steiner path cover $C'$ with respect to T which does not contain paths p and $p'$ satisfying one of the properties (1)–(4), such that $|C| \ge |C'|$ and $\mathfrak {s}(C) \ge \mathfrak {s}(C')$ holds.

• 1. $p=(x, \ldots )$ or $p=(\ldots , x)$ where $x \not \in T$. Comment: No path starts or ends with a Steiner vertex.

• 2. $p=(\ldots , u, x, v, \ldots )$ where $u \in V(A)$, $v \in V(B)$, and $x \not \in T$. Comment: On a path, the neighbors u, v of a Steiner vertex x are both contained in the same digraph.

• 3. $p=(\ldots ,x)$, $p'=(u, \ldots )$, where $x \in V(A)$, $u \in V(B)$, $p \ne p'$. Comment: There is no path p that ends in A, if there is a path $p' \ne p$ that starts in B.

• 4. $p=(\ldots , x, u, v, y, \ldots )$ where $u,v \not \in T$. Comment: The paths contain no edge between two Steiner vertices.

If $G = A \otimes B$ then cover $C'$ also does not contain paths satisfying properties (5)–(8).

• 5. $p=(x, \ldots )$, $p'=(u, \ldots )$, where $x \in V(A)$, $u \in V(B)$, $p \ne p'$. Comment: All paths start in the same digraph.

• 6. $p=(\ldots , x, y, \ldots )$, $p'=(\ldots , u, v, \ldots )$ where $x,y \in V(A)$, $u, v \in V(B)$. Comment: The cover $C'$ contains edges of only one of the digraphs.

• 7. $p=(x, \ldots )$, $p'=(\ldots , u, y, v, \ldots )$, where $x,y \in V(A)$, $u, v \in V(B)$, and $y \not \in T$. Comment: If a path starts in A then there is no Steiner vertex in A with two neighbors on the path in B.

• 8. $p=(x, \ldots )$, $p'=(\ldots , u, v, \ldots )$, where $x \in V(A)$ and $u, v \in V(B)$. Comment: If a path starts in A, then no edge of B is contained in the cover.

The proof of Lemma 1 is omitted due to space restrictions. Since the hypothesis of Lemma 1 is symmetric in A and B, the statement of Lemma 1 is also valid for co-graphs $G = A \otimes B$ if A and B are switched.

Definition 2

A directed Steiner path cover C for some directed co-graph $G = A \otimes B$ or $G = A \oslash B$ is said to be in normal form if it satisfies all properties (1)–(8) given in Lemma 1.

In the following we assume that a directed Steiner path cover for some directed co-graph $G = A \oslash B$ or $G = A \otimes B$ is always in normal form.

3 Algorithms for the Directed Steiner Path Cover Problem

3.1 Computing the Optimal Number of Paths

Lemma 2

Let A and B be two vertex-disjoint digraphs and let $T_A \subseteq V(A)$ and $T_B \subseteq V(B)$ be two sets of terminal vertices. Then, the following equations hold:

• 1. $p(\bullet _v, \emptyset )=0$ and $p(\bullet _v, \{v\})=1$

• 2. $p(A \oplus B, T_A \cup T_B) = p(A, T_A) + p(B, T_B)$

• 3. $p(A \otimes B, \emptyset ) = 0$

• 4. $p(A \otimes B, T_A \cup T_B) = \max \{1, p(B, T_B) - |V(A)|\}$ if $1 \le |T_B|$ and $|T_A| \le |T_B|$

• 5. $p(A \otimes B, T_A \cup T_B) = \max \{1, p(A, T_A) - |V(B)|\}$ if $1 \le |T_A|$ and $|T_A| > |T_B|$

• 6. $p(A \oslash B, T_A \cup T_B) = p(A, T_A)$ if $p(A) \ge p(B)$

• 7. $p(A \oslash B, T_A \cup T_B) = p(B, T_B)$ if $p(A) < p(B)$

Proof

1.–3. Obvious.

• 4. We show that $p(A \otimes B) \ge \max \{1,p(B)-|V(A)|\}$ applies by an indirect proof. Assume a directed Steiner path cover C for $A \otimes B$ has less than $\max \{1,p(B) - |V(A)|\}$ paths. The removal of all vertices of A from all paths in C gives a directed Steiner path cover of size $|C| + |V(A)| < p(B)$ for B.

  To see that $p(A \otimes B) \le \max \{1, p(B) - |V(A)|\}$ applies, consider that we can use any vertex of A to combine two paths of the cover of B to one path, since the series composition of A and B creates all directed edges between A and B. If there are more terminal vertices in A than there are paths in the cover of B, i.e. $p(B) < |T_A|$, then we have to split paths of B and reconnect them by terminal vertices of A. This can always be done since $|T_A| \le |T_B|$.

• 5. Similar to 4.

• 6. To see that $p(A \oslash B) \le p(A)$ applies, consider that we can connect each path of A by each path of B, see Lemma 1(3). Since no edge between B and A is created, no path of B can be extended by a path of A.

  We show that $p(A \oslash B) \ge p(A)$ applies by an indirect proof. Assume a directed Steiner path cover C for $A \oslash B$ contains less than p(A) paths. The removal of all vertices of B from all paths in C gives a Steiner path cover of size $|C| < p(A)$.

• 7. Similar to 6.   $\square$

3.2 Computing the Optimal Number of Steiner Vertices

Remark 1

For two vertex-disjoint directed co-graphs A, B and two sets of terminal vertices $T_A \subseteq V(A)$, $T_B \subseteq V(B)$ it holds that $s(A \oplus B, T_A \cup T_B) = s(A, T_A) + s(B, T_B)$, since the disjoint union does not create any new edges.

Remark 2

Let $G=A \oslash B$ be a directed co-graph, and let C be a directed Steiner path cover of G such that $p=(q_1,u_1,x,q_2,v_1)$ is a path in A, $p_1=(u_2, q_3)$ and $p_2=(v_2,q_4)$ are paths in B, all paths are vertex-disjoint paths in C, where $x \not \in T$, $u_1,u_2,v_1,v_2 \in T$, and $q_1,\ldots ,q_4$ are subpaths. Then, we can split p at vertex x into two paths, combine them with $p_1$ and $p_2$ to get $(q_1,u_1,u_2,q_3)$ and $(q_2,v_1,v_2,q_4)$ as new paths and we get a Steiner path cover without increasing the number of paths and one Steiner vertex less than C. If A and B are switched we get $(u_2,q_3,q_1,u_1)$ and $(v_2,q_4,q_2,v_1)$ as new paths and the statement also holds.

Next, we give the central lemma of our work, which is proven by induction on the structure of the directed co-graph.

Lemma 3

For every directed co-graph G and every directed Steiner path cover C for G with respect to a set T of terminal vertices it holds that $p(G) + s(G) \le |C| + \mathfrak {s}(C)$.

Proof

The statement is obviously valid for all directed co-graphs which consist of only one vertex. Let us assume that the statement is valid for directed co-graphs of n vertices. Let A and B are vertex-disjoint directed co-graphs of at most n vertices each.

Let $G = A \oplus B$ be a directed co-graph that consists of more than n vertices. By Lemma 2, and Remark 1, it holds that $p(A \oplus B) +s(A \oplus B) = p(A) + p(B) + s(A) + s(B)$. By the induction hypothesis, it holds that $p(A) + s(A) \le |C_{|A}| + \mathfrak {s}(C_{|A})$ and $p(B) + s(B) \le |C_{|B}| + \mathfrak {s}(C_{|B})$, where $C_{|A}$ denotes the cover C restricted to digraph A, i.e. the cover that results from C when all vertices of B are removed. Then, the statement of the lemma follows.

Let $G = A \otimes B$ be a directed co-graph that consists of more than n vertices. Without loss of generality, let $|T_A| \le |T_B|$.

• 1. Let X(A) denote the vertices of A used in cover C, and let D denote the cover for B that we obtain by removing the vertices of X(A) from cover C. By induction hypothesis, it holds that $p(B) + s(B) \le |D| + \mathfrak {s}(D)$.

• 2. Let nt(X(A)) denote the number of non-terminal vertices of X(A). Since covers are in normal form it holds that $\mathfrak {s}(C) = \mathfrak {s}(D) + nt(X(A))$ and $|C| = |D| - |T_A| - nt(X(A))$. Thus, we get $|C| + \mathfrak {s}(C) = |D| + \mathfrak {s}(D) - |T_A|$.

We put these two results together and obtain:

$$ p(B) + s(B) - |T_A| \le |D| + \mathfrak {s}(D) - |T_A| = |C| + \mathfrak {s}(C) $$

To show the statement of the lemma, we first consider the case $p(B) - 1 \le |V(A)|$. Then, it holds that $p(A \otimes B) = 1$. If $|T_A| \ge p(B) - 1$, then $d := |T_A| - (p(B)-1)$ many Steiner vertices from B, if available, can be replaced by terminal vertices from A. Otherwise if $|T_A| < p(B) - 1$, then $-d = (p(B) - 1) - |T_A|$ many Steiner vertices from A are used to combine the paths. Thus, it holds that $s(A \otimes B) \le \max \{0,s(B) - d\}$ since the number of Steiner vertices in an optimal cover is at most the number of Steiner vertices in a certain cover. Thus, since $p(A \otimes B) = 1$ we get for $s(B)\ge d$:

If $s(B)< d$ then all Steiner vertices of B can be replaced by terminal vertices of A and since $|T_A| \le |T_B|$ holds, some of the paths of B can be reconnected by the remaining terminal vertices of A. Thus, $p(A \otimes B) + s(A \otimes B)=1\le |C| + \mathfrak {s}(C)$ holds.

Consider now the case where $p(B) - 1 > |V(A)|$ holds, i.e. not all paths in an optimal cover for B can be combined by vertices of A. By Lemma  2, it holds that $p(A \otimes B) = \max \{1, p(B) - |V(A)|\}$. Thus, for $p(A \otimes B) > 1$ we get:

$$\begin{aligned} p(A \otimes B) + s(A \otimes B)\le & {} p(B) - |V(A)| + s(B) + nt(A) \\= & {} p(B) + s(B) - |T_A| ~ \le ~ |C| + \mathfrak {s}(C) \end{aligned}$$

The non-terminal vertices of A must be used to combine paths of the cover, thus the non-terminal vertices of A become Steiner vertices.

Let $G = A \oslash B$ be a directed co-graph that consists of more than n vertices. By the induction hypothesis, it holds that $p(A) + s(A) \le |C_{|A}| + \mathfrak {s}(C_{|A})$ and $p(B) + s(B) \le |C_{|B}| + \mathfrak {s}(C_{|B})$.

First, we consider the case $p(A) > p(B)$. By Lemma 2 it holds $p(A \oslash B) = p(A)$. We can connect every path of A with every path of B. By Remark 2 it holds that if there are more paths in A than in B, for each additional path in A we can remove one Steiner vertex from B. And since an optimal cover has at most as many Steiner vertices as a concrete cover, it holds that $s(A \oslash B) \le \mathfrak {s}(C_{|A}) + \mathfrak {s}(C_{|B}) - \min \{\mathfrak {s}(C_{|B}), |C_{|A}| - |C_{|B}|\}$. If we sum up both equations, we get

$$ p(A \oslash B) + s(A \oslash B) \le p(A) + \mathfrak {s}(C_{|A}) + \mathfrak {s}(C_{|B}) - \min \{\mathfrak {s}(C_{|B}), |C_{|A}| - |C_{|B}|\} $$

If $\mathfrak {s}(C_{|B}) \ge |C_{|A}| - |C_{|B}|$ holds, and since $\mathfrak {s}(C) = \mathfrak {s}(C_{|A}) + \mathfrak {s}(C_{|B})$ holds, we get

$$ p(A \oslash B) + s(A \oslash B) \le p(A) + \mathfrak {s}(C) - |C_{|A}| + |C_{|B}|. $$

The statement would be shown if $p(A) - |C_{|A}| + |C_{|B}| \le |C|$ would apply. It holds that $p(A) \le |C_{|A}|$, since an optimal cover has at most as many paths as a concrete cover, and it holds that $|C_{|B}| \le |C|$, since $|C| = \max \{|C_{|A}|, |C_{|B}|\}$ and the covers are in normal form. We sum up these equations and we get $p(A) + |C_{|B}| \le |C_{|A}| + |C|$, which is equivalent to $p(A) - |C_{|A}| + |C_{|B}| \le |C|$, thus $p(A \oslash B) + s(A \oslash B) \le |C| + \mathfrak {s}(C)$ has been shown.

If $\mathfrak {s}(C_{|B}) < |C_{|A}| - |C_{|B}|$, then it holds that $p(A \oslash B) + s(A \oslash B) \le p(A) + \mathfrak {s}(C_{|A})$, and we have to show that $p(A) + \mathfrak {s}(C_{|A}) \le |C| + \mathfrak {s}(C)$ applies. It holds that $p(A) \le |C_{|A}|$, since an optimal cover has at most as many paths as a concrete cover, and it holds that $|C_{|A}| \le |C|$, since $|C| = \max \{|C_{|A}|, |C_{|B}|\}$ and the covers are in normal form. Furthermore, it holds that $\mathfrak {s}(C_{|A}) \le \mathfrak {s}(C)$, since a part is only as big as the whole.

The other case $p(A) \le p(B)$ can be shown in a similar way.    $\square$

Remark 3

Let G be a directed co-graph and let C be a directed Steiner path cover for G with respect to some set of terminal vertices T. Then $\mathfrak {s}(C) \ge s(G)$ holds only if $|C| = p(G)$. If $|C| > p(G)$ then $\mathfrak {s}(C)$ might be smaller than s(G).

This fact will be used in the proof of the next lemma.

Lemma 4

Let A and B be two vertex-disjoint digraphs, and let $T_A \subseteq V(A)$, $T_B \subseteq V(A)$ be sets of terminal vertices. Then, the following equations hold:

• 1. $s(\bullet _v, \emptyset )=0$ and $s(\bullet _v, \{v\})=0$

• 2. $s(A \otimes B, T_A \cup T_B) = \max \{0, s(B, T_B) + p(B, T_B) - p(A \otimes B) - |T_A|\}$ if $|T_A| \le |T_B|$

• 3. $s(A \otimes B, T_A \cup T_B) = \max \{0,s(A, T_A) + p(A, T_A) - p(A \otimes B) - |T_B|\}$ if $|T_A| > |T_B|$

• 4. $s(A \oslash B, T_A \cup T_B) = s(A, T_A) + s(B, T_B)$ if $p(A, T_A) = p(B, T_B)$

• 5. $s(A \oslash B, T_A \cup T_B) = s(A) + s(B) - \min \{s(A), p(B)-p(A)\}$ if $p(A) < p(B)$

• 6. $s(A \oslash B, T_A \cup T_B) = s(A) + s(B) - \min \{s(B), p(A)-p(B)\}$ if $p(A) > p(B)$

Proof

• 1. Obvious.

• 2. First, we show $s(A \otimes B) \le \max \{0, s(B) + p(B) - p(A \otimes B) - |T_A|\}$. By Lemma 3, we know that $s(A \otimes B) + p(A \otimes B) \le \mathfrak {s}(C) + |C|$ holds for any cover C for co-graph $A \otimes B$ and any set of terminal vertices T. Consider cover C for $A \otimes B$ obtained by an optimal cover D for B in the following way.

Construction 1

We use the terminal vertices of A to either combine paths of D or to remove a Steiner vertex of D by replacing $v \not \in T$ by some terminal vertex of A in a path like $(\ldots , u, v, w, \ldots ) \in D$, where $u,w \in T$.

If $|T_A|\ge s(B)+p(B)$ then all paths of D can be combined and all Steiner vertices of D can be replaced by terminal vertices of A and since $|T_A|\le |T_B|$ holds, some of the paths can be split and reconnected by the remaining terminal vertices of A. Thus, $\mathfrak {s}(C) + |C|=1$ and $s(A \otimes B)=0$.

Otherwise, if $|T_A|< s(B)+p(B)$, then by Construction 1 we get $\mathfrak {s}(C) + |C| = s(B) + p(B) - |T_A|$, and by Lemma 3, we get the statement.

$$ \begin{array}{crcl} \!\!\!\!\!\!&{} s(A \otimes B) + p(A \otimes B) &{} \!\!\!\!\!\!\le &{}\!\!\!\!\! s(B) + p(B) - |T_A| ~ = ~ \mathfrak {s}(C) + |C| \\ \iff \!\!\!\!\!\!&{} s(A \otimes B) &{} \!\!\!\!\!\!\le &{}\!\!\!\!\! s(B) + p(B) - p(A \otimes B) - |T_A| \end{array} $$

Next, we prove $s(A \otimes B) \ge \max \{0, s(B) + p(B) - p(A \otimes B) - |T_A|\}$. Let X(A) be the vertices of V(A) that are contained in the paths of an optimal cover C for $A \otimes B$. Let D be the cover for B obtained by removing the vertices of X(A) from C. Since the covers are in normal form, the following holds:

$$ \begin{array}{crcl} \!\!\!\!\!\!&{} |X(A)| = nt(X(A)) + |T_A| &{}\!\!\!\!\!\! = &{}\!\!\!\!\! |D| - p(A \otimes B) \\ \iff \!\!\!\!\!\!&{} nt(X(A)) &{}\!\!\!\!\!\! = &{}\!\!\!\!\! |D| - p(A \otimes B) - |T_A| \end{array} $$

Thus, we get:

$$ \begin{array}{crcl} \!\!\!\!\!\!&{} s(A \otimes B) - nt(X(A)) ~ = ~ \mathfrak {s}(D) &{} \!\!\!\!\!\!= &{}\!\!\!\!\! s(A \otimes B) - |D| + p(A \otimes B) + |T_A| \\ \iff \!\!\!\!\!\!&{} s(A \otimes B) &{} \!\!\!\!\!\!= &{}\!\!\!\!\! \mathfrak {s}(D) + |D| - p(A \otimes B) - |T_A| \\ \Rightarrow \!\!\!\!\!\!&{} s(A \otimes B) &{} \!\!\!\!\!\!\ge &{}\!\!\!\!\! s(B) + p(B) - p(A \otimes B) - |T_A| \end{array} $$

The implication follows since by Lemma 3 it holds that $\mathfrak {s}(D) + |D| \ge s(B) +p(B)$.

• 3. Similar to 2.

• 4. To see that $s(A \oslash B) \le s(A) + s(B)$ applies, consider optimal covers C and D for A and B, respectively. We construct a cover E for $A \oslash B$ in the following way.

Construction 2

Connect each path of C by a path of D, see Lemma 1(3).

Since $|E| = p(A \oslash B)$ holds, we get $s(A \oslash B) \le \mathfrak {s}(E) = \mathfrak {s}(C) + \mathfrak {s}(D) = s(A) + s(B)$, because an optimal cover has at most as many Steiner vertices as a concrete cover.

To see that $s(A \oslash B) \ge s(A) + s(B)$ applies consider an optimal cover C for $A \oslash B$. Then, it holds that $s(A \oslash B) = \mathfrak {s}(C_{|A}) + \mathfrak {s}(C_{|B}) \ge s(A) + s(B)$, since $|C_{|A}| = p(A) = p( A \oslash B)= p(B) = |C_{|B}|$.

• 5. We have to distinguish two cases. First, let $s(A) > p(B) - p(A)$.

  To see that $s(A \oslash B) \le s(A) + s(B) - (p(B) - p(A))$ applies, consider optimal covers C and D for A and B. We construct a cover E for $A \oslash B$ as follows.

Construction 3

First, we split $p(B) - p(A)$ many paths of C at Steiner vertices as described in Remark 2. Afterwards, we connect each of the resulting paths by a path of D.

Thus, it holds that $|E| = p(A \oslash B) = p(B)$ and therefore $s(A \oslash B) \le \mathfrak {s}(C) + \mathfrak {s}(D) - (p(B) - p(A)) = s(A) + s(B) - (p(B) - p(A))$.

Please note, a Steiner path cover C for $A \oslash B$ with $\mathfrak {s}(C_{|A}) > 0$ is not optimal if $|C_{|A}| < |C| = p(A \oslash B)$ holds. By Remark 2 a path of $C_{|A}$ could be splitted at a Steiner vertex and the number of Steiner vertices could be reduced.

To see that $s(A \oslash B) \ge s(A) + s(B) - (p(B) - p(A))$ applies, consider an optimal cover C for $A \oslash B$. Then, it holds that $s(A \oslash B) = \mathfrak {s}(C) = \mathfrak {s}(C_{|A}) + \mathfrak {s}(C_{|B})$, and by the previous note it holds that $|C| = p(A \oslash B) = p(B) = |C_{|A}|$. By Lemma 3 we get $\mathfrak {s}(C_{|A}) + |C_{|A}| \ge s(A) + p(A)$. If we sum up these equations, we get $s(A \oslash B) + p(A \oslash B) = \mathfrak {s}(C_{|A}) + |C_{|A}| + \mathfrak {s}(C_{|B})$. Finally we get:

$$\begin{aligned} s(A \oslash B)= & {} \mathfrak {s}(C_{|A}) + |C_{|A}| - p(A \oslash B) + \mathfrak {s}(C_{|B}) \\\ge & {} s(A) + p(A) - p(B) + \mathfrak {s}(C_{|B}) ~ \ge ~ s(A) + p(A) - p(B) + s(B) \end{aligned}$$

Consider now the case that $s(A) \le p(B) - p(A)$. To see that $s(A \oslash B) \le s(B)$ applies, consider optimal covers C and D for A and B, respectively. We construct a cover E for $A \oslash B$ as follows.

Construction 4

First, we split as many paths of C at Steiner vertices as possible in a way described in Remark 2. Afterwards, all Steiner vertices of C have been removed and we connect each of the resulting paths by a path of D.

Thus, it holds that $|E| = p(A \oslash B) = p(B)$ and therefore $s(A \oslash B) \le \mathfrak {s}(E) = s(B)$.

To see that $s(A \oslash B) \ge s(B)$ applies, consider an optimal cover C for $A \oslash B$. By the above note it holds that $\mathfrak {s}(C_{|A}) = 0$, since C would not be optimal otherwise. Thus, we get $s(A \oslash B) = \mathfrak {s}(C_{|B}) \ge s(B)$, since $|C_{|B}| = p(B)$ holds and by Remark 3.

• 6. Similar to 5.    $\square$

By Lemmas 2 and 4, and since a directed co-tree can be computed in linear time from the input directed co-graph [6], we have shown the following result.

Theorem 1

Given some directed co-graph G, the values p(G) and s(G) can be computed in linear time with respect to the size of a directed co-expression for G.

3.3 Computing an Optimal Directed Steiner Path Cover

Next, we sketch an algorithm to compute a solution for the Directed Steiner Path Cover problem for some given directed co-graph G represented by its binary directed co-tree T(G). By performing the rules given in Construction 1–4 bottom-up along T(G), we compute the directed Steiner path cover for G. In order to obtain a linear running time $\mathcal {O}(|V(G)| + |E(G)|)$, we store the paths using double-linked, linear lists. While the paths that contain Steiner vertices are stored in one set and the paths that contain no Steiner vertices are stored in another set. The lists each have a pointer to the first and last element, which are terminal vertices by Lemma 1(1), and they have a pointer to the first and last Steiner vertices. The Steiner vertices are additionally chained as a doubly linked list. Additionally, we store the number of terminal and Steiner vertices for each list. This allows us to perform each construction step in constant time.

Theorem 2

Given some directed co-graph G, a solution for the Directed Steiner Path Cover problem can be computed in linear time with respect to the size of a directed co-expression for G.

4 Conclusions

Our results for directed co-graphs can be transfered to undirected co-graphs, which are precisely those graphs that can be generated from the single vertex graph by disjoint union and join operations, see [5]. Given some undirected co-graph G, we can solve the Steiner path cover problem in linear time by replacing every edge $\{u,v\}$ of G by two anti-parallel directed edges (u, v) and (v, u) and applying our solution for directed co-graphs.

Since a directed Hamiltonian path exists in digraph G if and only if we have $T=V(G)$ and $p(G)=1$, our results imply the first linear time algorithm for the directed Hamiltonian path problem on directed co-graphs. This generalizes the known results for undirected co-graphs of Lin et al. [10].