# The Clique-Width of Minimal Series-Parallel Digraphs
## 3 Directed Clique-Width of Minimal Series-Parallel Digraphs (MSP DAGs)  
We recall the definition of an MSP DAG which is based on [14] to be the digraph that can be constructed starting from one vertex and recursively using two fundamental operations: series composition and parallel composition. **Definition 2** (MSP DAG [14]). : _An MSP DAG is defined recursively as follows:_  
1. _A DAG containing only one vertex is an MSP DAG._
2. _If_ \(G_{1}\) _and_ \(G_{2}\) _are two vertex-disjoint MSP DAGs, then the DAG constructed by each of the following two operations is also an MSP DAG:_ 1. _Parallel composition:_ \(G=G_{1}PG_{2}=(V(G_{1})\cup V(G_{2}),E(G_{1})\cup E(G_{2}))\)_._ 2. _Series composition:_ \(G=G_{1}SG_{2}=(V(G_{1})\cup V(G_{2}),E(G_{1})\cup E(G_{2})\cup T_{1}\times S_{ 2})\) _where_ \(T_{1}\) _is the set of sink vertices of_ \(G_{1}\) _and_ \(S_{2}\) _is the set of source vertices of_ \(G_{2}\)_._  
An MSP DAG \(G\) can be represented by a binary decomposition tree \(T(G)\) that reflects the construction of \(G\) starting with its vertices using series and parallel operations as follows:  
**Definition 3** (Binary decomposition tree of MSP DAGs). : _The binary decomposition tree \(T(G)\) for an MSP DAG \(G\) containing only one vertex \(v\) consists of a single node \(r\) (the root of \(T\)) labeled by \(v\)._  
_The binary decomposition tree \(T(G)\) for an MSP DAG \(G=G_{1}PG_{2}\) (\(G=G_{1}SG_{2}\)) consists of a copy \(T_{1}\) of the binary decomposition tree for \(G_{1}\), a copy \(T_{2}\) of the binary decomposition tree for \(G_{2}\), an additional node \(r\) (the root of \(T\)) labeled by \(P\) (\(S\)) and two additional edges between the roots of \(T_{1}\) and \(T_{2}\) and node \(r\). The root of \(T_{1}\) is the left child of \(r\) and the root of \(T_{2}\) is the right child of \(r\)._  
For some node \(u\) of \(T(G)\) we define by \(G[u]\) the subgraph of \(G\) defined by the subtree of \(T(G)\) rooted at \(u\). It is proven in [14] that the construction of \(T(G)\) when \(G\) is an MSP DAG can be completed in \(\mathcal{O}(|V(G)|+|E(G)|)\) time complexity. This binary decomposition tree of an MSP DAG is the key of defining a directed clique-width expression. **Example 2**. : _Figure 2 illustrates an example of an MSP DAG \(G\) and its binary decomposition tree \(T(G)\)._  
**Remark 1**. : _Since MSP DAGs can define orientations of large complete bipartite graphs the underlying undirected graphs are not \(K_{4}\)-minor free graphs. Thus, the underlying undirected graphs of MSP DAGs are not series-parallel graphs. Both graph classes are even incomparable. A more close  
Figure 2: (**a**) An MSP DAG \(G\) and (**b**) its binary decomposition tree \(T(G)\). relation can be shown for the set of edge series-parallel multidigraphs, ESP DAGs for short, which are also defined in [14] from the single arc graph by applying a parallel composition and a series composition. The underlying undirected graph of an ESP DAG is a series-parallel graph. Furthermore, a DAG \(G\) with a single source and a single sink is an ESP DAG if and only if its line digraph \(LD(G)\) is an MSP DAG [14]._  
**Notation 1**. : _In our directed clique-width expressions, we define an empty expression, denoted by \(\emptyset\), to be an expression of an empty set of vertices. For any expression \(t\), we consider that \(t\oplus\emptyset=t\), so \(\alpha_{i,j}(t\oplus\emptyset)=\alpha_{i,j}(t)\) and \(\rho_{i\to j}(t\oplus\emptyset)=\rho_{i\to j}(t)\)._  
In [16] it was shown that the directed clique-width of an MSP DAG is at most 7. Next we improve this bound. **Theorem 1**. : _Every MSP DAG \(G\) has directed clique-width at most 6._  
Proof. : Let \(G\) be an MSP DAG and \(T(G)\) be a binary decomposition tree for \(G\). We prove that \(G\) has directed clique-width at most 6 by defining a directed clique-width 6-expression for \(G\). We use the 6 labels for the vertices in \(G\) as follows (see Figure 3):  
* Label 1 is used for the set of non-isolated sources. * Label 2 is used for the set of non-isolated sinks.