# The Clique-Width of Minimal Series-Parallel Digraphs
## 2 Preliminaries  
A _directed graph_ (or a _digraph_ for short) \(G=(V,E)\) is defined by two sets. \(V(G)\), or simply \(V\), is the vertex set, and \(E(G)\), or simply \(E\), is the arc set. Every arc of \(E\) is an ordered pair of vertices of \(V\). The number \(n\) indicates to the number of vertices of \(G\) and the number \(m\) indicates to the number of arcs of \(G\). If \((x,y)\in E\) then \(x\) is called a _predecessor_ of \(y\) and \(y\) is called a _successor_ of \(x\). A vertex \(x\) is called a _source_ if \(x\) has no predecessor, and is called a _sink_ if \(x\) has no successor. Given a subset \(X\) of the vertex set \(V\), the subgraph induced by \(X\) will be denoted by \(G[X]\). A _path_ of length \(k\) is a sequence of vertices \(x_{1},x_{2},\ldots,x_{k}\) such that any two consecutive vertices form an arc. A path \(x_{1},x_{2},\ldots,x_{k}\) is called a _circuit_ if \(x_{1}=x_{k}\) and \(k\geq 2\). A _directed acyclic graph_, denoted by \(DAG\), is a digraph with no circuit.  
Directed clique-width measures the difficulty of decomposing a digraph into a special tree-structure. The directed clique-width of digraphs has been defined by [PERSON] and [PERSON] [1] as follows.  
**Definition 1** (Directed clique-width [1]).: _The directed clique-width of a digraph \(G\), \(d\)-cw\((G)\) for short, is the minimum number of labels needed to define \(G\) using the following four operations:_  
1. _Creation of a new vertex_ \(v\) _with label a (denoted by_ \(a(v)\)_)._
2. _Disjoint union of two vertex-disjoint labeled digraphs_ \(G\) _and_ \(H\) _(denoted by_ \(G\oplus H\)_)._
3. _Inserting an arc from every vertex with label a to every vertex with label_ \(b\) _(_\(a\
eq b\)_, denoted by_ \(\alpha_{a,b}\)_)._
4. _Change label_ \(a\) _into label_ \(b\) _(denoted by_ \(\rho_{a\to b}\)_)._ _An expression_ \(X\) _built with the operations defined above using_ \(k\) _labels is called_ \(a\) _directed clique-width_ \(k\)_-expression._  
**Example 1**.: _The directed clique-width of digraph \(G\) with vertex set \(V(G)=\{a,b,c,d\}\) and arc set \(E(G)=\{(a,b),(b,c),(c,d),(d,a),(d,b)\}\) shown in Figure 1 is at most 3, since it can be defined by the following directed clique-width 3-expression:_  
\[\alpha_{3,1}(\alpha_{2,3}(3(d)\oplus(\rho_{3\to 2}(\rho_{2\to 1}(\alpha_{2,3}(3(c)\oplus( \alpha_{1,2}(2(b)\oplus 1(a)))))))))\]  
Given a digraph \(G\) and an integer \(k\), deciding whether the directed clique-width of \(G\) is at most \(k\) is NP-complete [17]. In contrast to the undirected case, there are only very few digraph classes for which we know how to compute a directed clique-width expression in polynomial time. This holds for directed co-graphs [5], digraphs of bounded directed modular width [18], and orientations of trees [5]. In order to find directed clique-width expressions for general digraphs one can use results on the related parameter bi-rank-width [19]. By ([15], Lemma 9.9.12) we can use approximate directed clique-width expressions obtained from rank-decomposition with the drawback of a single-exponential blow-up on the parameter.  
Figure 1: Digraph defined by the directed clique-width 3-expression given in Example 1.