Similar to the tree-width (twd), the clique-width (cwd) is an invariant of graphs. A well known relationship between tree-width and clique-width is that cwd(G) ≤ 3 · 2twd(G)−1. It is also known that treewidth of Cactus graphs is 2, therefore the clique-width for those graphs is smaller or equal than 6. In this paper, it is shown that the clique-width of Cactus graphs is smaller or equal to 4 and we present a polynomial time algorithm which computes exactly a 4-expression.
The clique-width has recently become an important graph invariant in parameterized complexity theory because measures the difficulty of decomposing a graph in a kind of tree-structure, and thus efficiently solve certain graph problems if the graph has clique-width at most k. A decomposition of a graph G, to compute its clique-width, can be viewed as a finite term, Courcelle et al. [5] define a term based on a set of four operations such as: 1) the creation of vertices, 2) disjoint union of graphs, 3) edge creation and 4) re-labelling of vertices. The number of labels (vertices) used to build the graph is commonly denoted by k. A well defined combination of these operations, called k-expression, are necessary to build the graphs, which in turn defines clique-width. The clique-width or the corresponding decomposition of the graph is measured by means of a k-expression [12]. As the clique-width increases the complexity of the respective graph problem to solve increases too, in fact for some automata that represent certain graph problems (according to the scheme in Courcelle’s main theorem), computation runs out-of-memory, see [16] for some examples of graphs with the clique-width 3 or 4 .
It is important to search for an alternative graph decomposition that can be applied to a wider classes than to those of bounded tree-width and still preserve algorithmic properties. Tree decomposition and its tree-width parameter of a graph, are among the most commonly used concepts [7]. Therefore, clique-width can be seen as a generalization of tree-width in a sense that every graph class of bounded tree-width also have bounded clique-width [4].
In recent years, clique-width has been studied in different classes of graphs showing the behavior of this invariant under certain operations; the importance of the clique-width is that if a problem on graphs is bounded by this invariant it can be solved in linear time.
Regarding our present work, we are interested in the class of graphs, called cactus, which consist of non-edge intersecting fundamental cycles [11]. This class belongs to the class of bounded tree-width. These graphs have already a tree like structure, thus we can apply a well known result by Corneil and Rotics in [4], for any graph G, which is cwd(G) ≤ 3 · 2twd(G)−1, Thus we can obtain a bound for the clique-width of cactus graphs. It is also known that the tree-width of Cactus graphs is 2, so by using the latter inequality, the bound clique-width smaller or equal to 6 is obtained. Therefore, our main result in this paper is to show that the clique-width of Cactus graphs is smaller or equal to 4 improving the best known bound and also we present a polynomial time algorithm which computes the 4-expression. 2
All graphs in this work are simple i.e. finite with no self-loops nor multiple edges and are undirected. The degree of a vertex v in a graph G, is the number of edges of G incident with v. We denote by Δ(G) the maximum degree of the vertices of G.
A spanning tree of a connected graph on n vertices is a subset of n − 1 edges that form a tree. Given a graph G, let TG be one of its spanning trees. The edges in TG are called tree edges, whereas the edges in E(G)\E(TG) are called fronds. Let e ∈ E(G)\E(TG) be a frond edge, the union of the path in TG between the endpoints of e with the edge e itself forms a simple cycle, such cycle is called a basic (or fundamental) cycle of G with respect to TG. Each frond e = {x, y} holds the maximum path contained in the basic cycle that it is part of.
Two cycles that are non-intersected are called independent, i.e. two independent cycles (Ci, Cj ) satisfy (E(Ci) ∩ E(Cj )) = ∅. The graphs consisting of independent cycles are known as Cactus Graphs and they appeared in the scientific literature more than half a century ago under the name of Husimi trees [11]. The cactus graphs can be syntactically recognized as connected graphs in which no edge lies in more than one simple cycle. Consequently, each part of a cactus graph is either an edge or a simple cycle. Cactus graphs have many applications, for example, in the modeling of wireless sensor networks [1] and in the comparison of genomes [17]. Nowadays, cactus graphs have attracted attention because some NP-hard resource allocation problems were found to be solved in polynomial time for this class of graphs.
We now introduce the notion of clique-width (cwd, for short).
Let C be a countable set of labels. A labeled graph is a pair (G, γ) where γ maps V (G) into C . A labeled graph can be defined as a triple G = (V, E, γ) and its labeling function is denoted by γ(G). We say that G is C − labeled if C is finite and γ(G)(V ) ⊆ C. We denote by G (C) the set of undirected C − labeled graphs. A vertex with label a will be called an a − port.
We introduce the following symbols: a nullary symbol a(v) for every a ∈ C and v ∈ V ; a unary symbol ρa→b for all a, b ∈ C , with a 6= b; a unary symbol ηa,b for all a, b ∈ C , with a 6= b; a binary symbol ⊕.
These symbols are used to denote operations on graphs as follows: a(v) creates a vertex with label a corresponding to the vertex v, ρa→b renames the vertex a by b, ηa,b creates an edge between a and b, and ⊕ is a disjoint union of graphs.
For C ⊆ C we denote by T (C) the set of finite well-formed terms written with the symbols ⊕, a, ρa→b, ηa,b for all a, b ∈ C, where a 6= b. Each term in T (C) denotes a set of labeled undirected graphs. Since any two graphs denoted by the same term t are isomorphic, one can also consider that t defines a unique abstract graph. We let val(t) be the set of graphs denoted by t.
For every labeled graph G we let cwd(G) = min{|C||G ∈ val(t), t ∈ T (C)}. 3
Computing cwd(G) when G is a Cactus Graph Let G = (V, E) be a connected graph with n = |V |, m = |E| and such that Δ(G)≥ 2. Let C be the set of fundamental cycles of G. If two distinct fundamental cycles Ci and Cj from C have common edges then we say that both cycles are intersected, that is, Ci△Cj forms a new cycle, where △ denotes the symmetric difference operation between the set of edges in both cycles. In fact, Ci△Cj = (E(Ci) ∪ E(Cj)) − (E(Ci) ∩ E(Cj)) constitutes a composed cycle. A unicyclic graph G is one where C consists of a singleton e.g. G contains a single independent cycle. A cactus graph G is one where C consists of independent cycles.
In this section we show that the clique-width of cactus graphs is smaller or equal than 4. We firstly show how to compute the clique-width of unicyclic graphs and then we extend the algorithm for cactus graphs.
Definition 1. Let {Gi}i∈I be a family of graphs, a joint v ∈/ Gif oreachGi ∈ {Gi} is a vertex such that Gv = (V ({Gi}i∈I ) ∪ {v}, E({Gi}i∈I) ∪ {vvi}) for at least one vi in each {Gi}i∈I . In other words Gv is built from the family {Gi}i∈I and a new vertex v.
Proof. Let G = Cn S{Ti}i∈I for some family {Ti}i∈I of trees. Compute the kexpression for each {Ti}i∈I without the joining vertex to Cn. It is well known that cwd({Ti}i∈I) ≤ 3 for each Ti, i ∈ I. Relabel the k-expression of each {Ti}i∈I in order to use exactly two labels. One label for the root and the other label for the rest of the vertices of the tree. It is also well known that cwd(Cn) ≤ 4. We show how to combine the labels in order to compute the clique-width of G. Assume that a and b are used as labels of the root and the rest of the vertices of each tree respectively. Let c and d be the free allowed labels to be used. We built the k-expression of Cn beginning with a joint vertex v. Make a label c(v). * Built the disjoint union of c(v) and each tree {Ti}i∈I for which v is joint that is c(v) L{Ti}i∈I . Make an edge between c and the root label of each tree {Ti}i∈I for which v is joint, that is ηc,a. Relabel the root vertex of each {Ti}i∈I by b, i.e ρa→b. That means that the available labels are a and d. Since c(v) is the label of the initial vertex of Cn it must have a unique label to close the cycle. We rename c by d, i.e. ρc→d, so we have the free labels a and c. We use a and c to built the path from d to the next joint vertex, it can be done by alternating the labels and making an edge between them, those vertices whose unique edge in the cycle have been built are relabeled by b. There are two possible labels for the next joint vertex a or c. In any case we can relabel the joint vertex such that it is always c (if it is c there is nothing to be done, if it is a we change c by b and a by c).
We repeat the process from * to joint the new trees {Ti}i∈I . When the last joint vertex c(v) is reached, the k-expression from c(v) to d is built, using the labels a,b and c.
Algorithm 1 shows the procedure to compute the k-expression of an unicyclic graph.
Algorithm 1 Procedure that computes k-expression(G) when G is unicyclic. 1: procedure k-expression(G) 2: let (C be the unique cycle of G) 3: for each tree {Ti}i∈I \ C of G {paths are included} do 4: {Ti}i∈I = {Ti}i∈I -expression({Ti}i∈I ) {it is well known that cwd({Ti}i∈I ) ≤ 3} 5: Relabel the root of {Ti}i∈I by a and relabel the remaining vertices by b 6: end for 7: k = ∅ 8: for each joint vertex v of C {the join is given with some trees {Ti}i∈I } do 9: c(v){Make a new node label} 10: k = c(v) L{Ti}i∈I L k 11: ηc,a(k) {Make an edge from the node of the cycle to each tree {Ti}i∈I who is joined with} 12: ρa→b(k) {Relabel a by b in the new graphs to free a label} 13: if v is the first joint vertex then 14: ρc→d(k) {Relabel c by d in the new graph to remember the initial node of the cycle} 15: end if 16: add to k the k-expression of path(v, w) \ w where w is the nearest joint vertex of v {Use the labels a and c to build the edges and b to rename the interior vertices of path(v, w) \ w, such that the last vertex is label with a and the other vertices with b they are enough since cwd(Pn) ≤ 3} 17: end for 18: ηc,d(k) {Close the cycle}
We now describe how to compute the clique-width when G is Cactus. A depth first search spanning tree is a spanning tree built using the depth-first traversal algorithm, also a depth first search graph is defined. Let G = (V, E) be a connected graph, and TG a depth first search spanning tree whose set of fundamental cycles C are independent, then an enumeration of C is computed as follows:
2. For each C ∈ C, C 6= C1 compute min{|path(v, w)| | ∀v ∈ C1, ∀w ∈ C} where path(v, w) are the edges in the path from v to w in TG.
Sort the elements of C by its minimal path with respect to C1. Elements of C with the same minimal path can be sorted randomly.
A partition of G into unicyclic graphs is defined as follows: Definition 2. Let G be a cactus graph, a family of subgraphs {{Gi}i∈I } of G is built as follows: 1. A depth first search graph is built over G, choosing an x ∈ C1 as the root node, starting the search, for instance, with the node x with minimum degree, and selecting among different potential nodes to visit, the node with lowest degree first and with lowest index in its label as a second criterion. Then, we obtain a unique depth first search graph G′ (in the set of all possible depth-first graphs), which we denote here as G′ = df s(G). 2. For each Ci ∈ C
Gi = Ci Sv∈Ci {path(v, w) | (w is a leaf or w ∈ Cj ∈ C, i 6= j) and 6 ∃x ∈ Ck, x ∈ path(v, w), k 6= j} Lemma 2. If G be a cactus graph, then the family of subgraphs {Gi}i∈I over G by Definitions 2 forms a set partition of E(G).
Proof. Let X, Y ∈ ∪{Gi}i∈I , X 6= Y , then by definition X ∩ Y = ∅. If X or Y are unitary, assuming X = {e}, e is not member of Y because cycle(e) is independent in G and has no common edges with any other cycle in G. If X and Y are not unitary then they have no common edges because in other case, we can build S with the common edges of X and Y and S holds the condition in Definition 2, and then X = Y .
Due to each element e ∈ E(G) belong to a unique partition then ∪{Gi}i∈I =
Lemma 3. Let G be a cactus graph and {Gi}i∈I a family of subgraphs over G as specified in Definitions 2. For each pair of graphs Gk, Gj in {Gi}i∈I , either V (Gk) ∩ V (Gj ) = ∅ or V (Gk) ∩ V (Gj ) = {v} is a singleton.
Proof. By contradiction suppose that V (Gk) ∩ V (Gj ) 6= ∅ and V (Gk) ∩ V (Gj ) 6= {v} it means that there are at least two vertices, let say v1, v2 in the intersection, that the edge e = (v1, v2) belongs to the intersection, contradicting the hypothesis that Gk and Gj have a set of disjoint edges.
Algorithm 2 Procedure that computes cwd(G) when G is a cactus graph, from the set of unicycle graphs Gj such that G = S Gj . Proof. Let G = S Gj where each Gj is unicyclic. The clique-width of each Gj is smaller of equal to 4, i.e cwd(Gj ) ≤ 4. Line 2 of algorithm 2 begins with the Gj who have exactly one joint vertex v. So the k-expression of each Gj \ v can be rewritten with two labels, one is used for the vertices to be joint with v and the other for the rest of the vertices. The next steps in the construction of the k-expression is similar to the one of unicyclic graphs substituting trees {Ti}i∈I for unicyclic graphs {Gi}i∈I who has more than one joint vertex. 4
We discuss the time complexity of Algorithm 2 which is the main result reported in this paper. The complexity of Algorithm 2 in the worst case is |C| which is the number of independent cycles of the graph. The worst case time complexity of Algorithm 1 is |V ({Gi}i∈I )| = n when there is a unique unicyclic. 5
We present an example of the application of Algorithm 2. Let us consider the graph G:
According to the partition procedure, the graph is partitioned in the three subgraphs shown below: , 3 G2 10 5 , 5 6 10 7 G3
The k-expression of G3 \ {5} is: ρc→a(ηa,c(ηb,a(b(
ρc→a(ρd→a(ηd,c(ρc→d(ρa→b(ηc,a(kG3\{5}) ⊕ c(
k = ρa→b(ηc,a(ρc→a(ηd,c(ρc→d(ρa→b(ηa,c(kG3∪G2\3 ⊕ c(
a(
b(
Computing the clique-width of a graph G is a classic NP-complete problem for general graphs. We establish that if the depth-first graph of a given graph G has no intersected cycles, e.g. it is Cactus then the computation of cwd(G) is a tractable problem. Even more cwd(G) ≤ 4.