# The Clique-Width of Minimal Series-Parallel Digraphs
## 3 Directed Clique-Width of Minimal Series-Parallel Digraphs (MSP DAGs)
At most one of the expressions \(t_{1}(\alpha)\) and \(t_{2}(\alpha)\) may be empty. The labels at the end of the computation of \(t_{1}(\alpha)\) or \(t_{2}(\alpha)\) represent implicitly whether the corresponding vertices are non-isolated sources (labeled by 1), non-isolated sinks (labeled by 2), vertices that are not sources and not sinks (labeled by 3), or isolated vertices (labeled by 4) in \(G[\alpha]\). Initially, in Step 3, every vertex is labeled by 4 since the subgraph induced by a leaf of \(T(G)\) consists only of one isolated vertex. Step 5 determines the left child \(\alpha_{1}\) and the right child \(\alpha_{2}\) of an internal node \(\alpha\). Steps 7 and 8 construct the expression \(t_{1}(\alpha)\) and \(t_{2}(\alpha)\) for a \(P\)-node \(\alpha\) to be respectively the disjoint union of \(t_{1}(\alpha_{1})\), \(t_{1}(\alpha_{2})\) and the disjoint union of \(t_{2}(\alpha_{1})\), \(t_{2}(\alpha_{2})\). Steps 10-14 construct the expressions \(t_{1}(\alpha)\) and \(t_{2}(\alpha)\) for an \(S\)-node \(\alpha\) as follows: Step 10 changes the label of isolated vertices of \(G[\alpha_{2}]\) from 4 to 2 and inserts all arcs from an isolated vertex of \(G[\alpha_{1}]\) to an isolated vertex of \(G[\alpha_{2}]\); Step 11 changes the label of non-isolated sinks of \(G[\alpha_{1}]\) from 2 to (auxiliary label) 5 and inserts all arcs from a non-isolated sink of \(G[\alpha_{1}]\) to an isolated vertex of \(G[\alpha_{2}]\); Step 12, changes the label of non-isolated sources of \(G[\alpha_{2}]\) from 1 to (auxiliary label) 6 and inserts all arcs from an isolated vertex of \(G[\alpha_{1}]\) to a non-isolated source of \(G[\alpha_{2}]\) and all arcs from a non-isolated sink of \(G[\alpha_{1}]\) to a non-isolated source of \(G[\alpha_{2}]\). Step 13, changes the label of every isolated vertex of \(G[\alpha_{1}]\) from 4 to 1 since these vertices are non-isolated sources in \(G[\alpha]\), changes the label of every non-isolated sink of \(G[\alpha_{1}]\) from 5 to 3, since these vertices are neither sources nor sinks in \(G[\alpha]\), and changes the label of every non-isolated source of \(G[\alpha_{2}]\) from 6 to 3, since these vertices are also neither sources nor sinks in \(G[\alpha]\). The expression \(t_{2}(\alpha)\) must be empty because of \(G[\alpha]\) is connected. Since the number of nodes in \(T(G)\) is \(\mathcal{O}(n)\) and every step can be done in \(\mathcal{O}(1)\) time, the total time complexity of Algorithm 1 is in \(\mathcal{O}(n)\). Corollary 1: _For every MSP DAG \(G\) which is given by its binary decomposition tree \(T(G)\) a directed clique-width \(6\)-expression can be found in time \(\mathcal{O}(|V(G)|)\)._  
```
Input A binary decomposition tree \(T(G)\) of an MSP DAG \(G\). Output A directed clique-width \(6\)-expression of \(G\). Let \(\alpha\) be a node on a post-order traversal of \(T(G)\). 1:if\(\alpha\) is a leaf representing vertex \(v\)then
2:\(t_{1}(\alpha)=\emptyset\)
3:\(t_{2}(\alpha)=4(v)\)
4:else
5: let \(\alpha_{1}\) and \(\alpha_{2}\) be respectively the left and right children of \(\alpha\)
6:if\(\alpha\) is a \(P\)-node then
7:\(t_{1}(\alpha)=t_{1}(\alpha_{1})\oplus t_{1}(\alpha_{2})\)
8:\(t_{2}(\alpha)=t_{2}(\alpha_{1})\oplus t_{2}(\alpha_{2})\)\(\triangleright\)\(\alpha\) is an \(S\)-node
9:else
10:\(E_{1}=\alpha_{4,2}(t_{2}(\alpha_{1})\oplus\rho_{4\to 2}(t_{2}(\alpha_{2})))\)\(\triangleright\) arcs from \(t_{2}(\alpha_{1})\) to \(t_{2}(\alpha_{2})\)
11:\(E_{2}=\alpha_{5,2}(\rho_{2\to 5}(t_{1}(\alpha_{1}))\oplus E_{1})\)\(\triangleright\) arcs from \(t_{1}(\alpha_{1})\) to \(t_{2}(\alpha_{2})\)
12:\(E_{3}=\alpha_{4,6}(\alpha_{5,6}(E_{2}\oplus\rho_{1\to 6}(t_{1}(\alpha_{2}))))\)\(\triangleright\) arcs from \(t_{1}(\alpha_{1})\) and \(t_{2}(\alpha_{1})\) to \(t_{1}(\alpha_{2})\)
13:\(t_{1}(\alpha)=\rho_{6\to 3}(\rho_{5\to 3}(\rho_{4\to 1}(E_{3})))\)\(\triangleright\) relabeling
14:\(t_{2}(\alpha)=\emptyset\)
```  
**Algorithm 1** Construction directed clique-width \(6\)-expression of an MSP DAG  
**Example 3**.