Polynomial-time Algorithm for Isomorphism of
Graphs with Clique-width at most Three

arXiv:1506.01695v2 [cs.CC] 28 Apr 2016

Bireswar Das? , Murali Krishna Enduri?? and I. Vinod Reddy
IIT Gandhinagar, India
{bireswar,endurimuralikrishna,reddy vinod}@iitgn.ac.in

Abstract. The clique-width is a measure of complexity of decomposing
graphs into certain tree-like structures. The class of graphs with bounded
clique-width contains bounded tree-width graphs. We give a polynomial
time graph isomorphism algorithm for graphs with clique-width at most
three. Our work is independent of the work by Grohe et al. [16] showing
that the isomorphism problem for graphs of bounded clique-width is
polynomial time.

1

Introduction

Two graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are isomorphic if there is a bijection f : V1 → V2 such that {u, v} ∈ E1 if and only if {f (u), f (v)} ∈ E2 . Given
a pair of graphs as input the problem of deciding if the two graphs are isomorphic is known as graph isomorphism problem (GI). Despite nearly five decades
of research the complexity status of this problem still remains unknown. The
graph isomorphism problem is not known to be in P. It is in NP but very unlikely to be NP-complete [5]. The problem is not even known to be hard for P.
Recently Babai [2] designed a quasi-polynomial time
algorithm to solve the GI
√
O( n log n)
problem improving the previously best known 2
time algorithm [1,25].
Although the complexity of the general graph isomorphism problem remains elusive, many polynomial time algorithms are known for restricted classes of graphs
e.g., bounded degree [20], bounded genus [22], bounded tree-width [3], etc.
The graph parameter clique-width, introduced by Courcelle et al. in [7], has
been studied extensively. The class of bounded clique-width graphs is fairly large
in the sense that it contains distance hereditary graphs, bounded tree-width
graphs, bounded rank-width graphs [18], etc. Fellows et al. [14] shows that the
computing the clique-width of a graph is NP-hard. Oum and Seymour [23] gave
an elegant algorithm that computes a (23k+2 − 1)-expression for a graph G of
clique-width at most k or decides that the clique-width is more than k.
The parameters tree-width and clique-width share some similarities, for example many NP-complete problems admit polynomial time algorithms when the
tree-width or the clique-width of the input graph is bounded. A polynomial time
?
??

Part of the research was done while the author was a DIMACS postdoctoral fellow.
Supported by Tata Consultancy Services (TCS) research fellowship.

isomorphism algorithm for bounded tree-width graphs has been known for a long
time [3]. Recently Lokhstanov et al. [19] gave an fpt algorithm for GI parameterized by tree-width. The scenario is different for bounded clique-width graphs.
The complexity of GI for bounded clique-width graphs is not known. Polynomial
time algorithm for GI for graphs with clique-width at most 2, which coincides
with the class of co-graphs, is known probably as a folklore. The complexity of
recognizing graphs with clique-width at most three was unknown until Corneil
et al. [6] came up with the first polynomial time algorithm. Their algorithm
(henceforth called the CHLRR algorithm) works via an extensive study of the
structure of such graphs using split and modular decompositions. Apart from
recognition, the CHLRR algorithm also produces a 3-expression for graphs with
clique-width at most three. For fixed k > 3, though algorithms to recognize
graphs with clique-width at most k are known [23], computing a k-expression is
still open. Recently in an independent work by Grohe et al. [16] designed an isomorphism algorithm for graphs of bounded clique-width subsuming our result.
Their algorithm uses group theory techniques and has worse runtime. However
our algorithm has better runtime and uses different simpler intuitive techniques.
In this paper we give isomorphism algorithm for graphs with clique-width
at most three with runtime O(n3 m). Our algorithm works via first defining
a notion of equivalent k-expression and designing O(n3 ) algorithm to test if
two input k-expressions are equivalent under this notion. Next we modify the
CHLRR algorithm slightly to output a linear sized set parseG of 4-expressions
for an input graph G of clique-width at most three which runs in O(n3 m) time.
Note that modified CHLRR algorithm will not output a canonical expression.
However we show that for two isomorphic graphs G and H of clique-width at
most three, parseG contains an equivalent k-expression for each k-expression in
parseH and vice versa. Moreover, if G and H are not isomorphic then no pair
in parseG × parseH is equivalent.

2

Preliminaries

In this paper, the graphs we consider are without multiple edges and self loops.
The complement of a graph G is denoted as G. The coconnected components of
G are the connected components of G. We say that a vertex v is universal to a
vertex set X if v is adjacent to all vertices in X \ {v}. A biclique is a bipartite
graph (G, X, Y ), such that every vertex in X is connected to every vertex of Y .
A labeled graph is a graph with labels assigned to vertices such that each vertex
has exactly one label. In a labeled graph G, lab(v) is the label of a vertex v and
lab(G) is the set of all labels. We say that a graph is bilabeled (trilabeled) if it is
labeled using exactly two (three) labels. The set of all edges between vertices of
label a and label b is denoted Eab . We say Eab is complete if it corresponds to a
biclique.
The subgraph of G induced by X ⊆ V (G) is denoted by G[X], the set
of vertices adjacent to v is denoted NG (v). The closed neighborhood NG [v] of
v is NG (v) ∪ {v}. We write G ∼
=f H if f is an isomorphism between graphs
2

G and H. For labeled graphs G and H, we write G ∼
=πf H if G ∼
=f H and
π : lab(G) → lab(H) is a bijection such that for all x ∈ V (G) if lab(x) = i then
lab(f (x)) = π(i). The set of all isomorphisms from G to H is denoted ISO(G, H).
Definition 1. The clique-width of a graph G is defined as the minimum number of labels needed to construct G using the following four operations:
i.
ii.
iii.
iv.

v(i): Creates a new vertex v with label i
G1 ⊕ G2 · · · ⊕ Gl : Disjoint union of labeled graphs G1 , G2 , · · · , Gl
ηi,j : Joins each vertex with label i to each vertex with label j (i 6= j)
ρi→j : Renames all vertices of label i with label j

Every graph can be constructed using the above four operations, which is represented by an algebraic expression known as k-expression, where k is the number
of labels used in expression. The clique-width of a graph G, denoted by cwd(G),
is the minimum k for which there exists a k-expression that defines the graph G.
From the k-expression of a graph we can construct a tree known as parse tree of
G. The leaves of the parse tree are vertices of G with their initial labels, and the
internal nodes correspond to the operations (ηi,j , ρi→j and ⊕) used to construct
G. For example, C5 (cycle of length 5) can be constructed by
η1,3 ((ρ3→2 (η2,3 ((η1,2 (a(1) ⊕ b(2))) ⊕ (η1,3 (c(3) ⊕ d(1)))))) ⊕ e(3)).
The k-expression for a graph need not be unique. The clique-width of any induced
subgraph is at most the clique-width of its graph [9].
Now we describe the notions of modular and split decompositions. A set
M ⊆ V (G) is called a module of G if all vertices of M have the same set of
neighbors in V (G) \ M . The trivial modules are V (G), and {v} for all v. In
a labeled graph, a module is said to be a l-module if all the vertices in the
module have the same label. A prime (l-prime) graph is a graph (labeled graph)
in which all modules (l-modules) are trivial. The modular decomposition of a
graph is one of the decomposition techniques which was introduced by Gallai
G
that has the
[15]. The modular decomposition of a graph G is a rooted tree TM
following properties:
G
1. The leaves of TM
are the vertices of G.
G
2. For an internal node h of TM
, let M (h) be the set of vertices of G that are
G
leaves of the subtree of TM rooted at h. (M (h) forms a module in G).
G
3. For each internal node h of TM
there is a graph Gh (representative graph)
with V (Gh ) = {h1 , h2 , · · · , hr }, where h1 , h2 , · · · , hr are the children of h in
G
TM
and for 1 ≤ i < j ≤ r, hi and hj are adjacent in Gh iff there are vertices
u ∈ M (hi ) and v ∈ M (hj ) that are adjacent in G.
4. Gh is either a clique, an independent set, or a prime graph and h is labeled Series if Gh is clique, Parallel if Gh is an independent set, and Prime
otherwise.

James et al. [17] gave first polynomial time algorithm for finding a modular
decomposition which runs in O(n4 ) time. Linear time algorithms to find modular
decompositions are proposed in [10,24].
3

A vertex partition (A, B) of a graph G is a split if Ã = A ∩ N (B) and B̃ =
B∩N (A) forms a biclique. A split is trivial if |A| or |B| is one. Split decomposition
was introduced by Cunningham [11]. Loosely it is the result of a recursive process
of decomposing a graph into components based on the splits. Cunningham [11]
showed that a graph can be decomposed uniquely into components that are stars,
cliques, or prime (i.e., without proper splits). This decomposition is known as
the skeleton. For details see [12]. A polynomial time algorithm for computing
the skeleton of a graph is given in [21].
Theorem 1. [12](see [6]) Let G be a connected graph. Then the skeleton of G is
unique, and the proper splits of G correspond to the special edges of its skeleton
and to the proper splits of its complete and star components.
Organization of the paper: In Section 3 we discuss GI-completeness of prime
graph isomorphism. In Section 4 we define a notion of equivalence of parse trees
called structural isomorphism, and give an algorithm to test if two parse trees
are structurally isomorphic. We give an overview of the CHLRR algorithm [6]
in Section 5. In Section 6, we present the isomorphism algorithm for prime
graphs of clique-width at most three. In Appendix, we show that the CHLRR
algorithm can be modified suitably to output structurally isomorphic parse trees
for isomorphic graphs.

3

Completeness of Prime Graph Isomorphism

It is known that isomorphism problem for prime graphs is GI-complete [4]. There
is an easy polynomial time many-one reduction from GI to prime graph isomorphism1 described in Lemma 9 of the Appendix. Unfortunately, this reduction
does not preserve the clique-width. We also give a clique-width preserving Turing reduction from GI to prime graph isomorphism which we use in our main
algorithm. The reduction hinges on the following lemma.
Lemma 1. [8] G is a graph of clique-width at most k iff each prime graph
associated with the modular decomposition of G is of clique-width at most k.
We next show that if we have an oracle for GI for colored prime graphs of cliquewidth at most k then there is a GI algorithm for graphs with clique-width at
most k.
Theorem 2. Let A0 be an algorithm that given two colored prime graphs G0
and H 0 of clique-width at most k, decides if G0 ∼
= H 0 via a color preserving
isomorphism. Then there exists an algorithm A that on input any colored graphs
G and H of clique-width at most k decides if G ∼
= H via a color preserving
isomorphism.
Proof. Let G and H be two colored graphs of clique-width at most k. The
algorithm is similar to [13], which proceeds in a bottom up approach in stages
1

In fact, it is an AC0 reduction

4

starting from the leaves to the root of the modular decomposition trees TG and
TH of G and H respectively. Each stage corresponds to a level in the modular
decomposition. In every level, the algorithm A maintains a table that stores
whether for each pair of nodes x and y in TG and TH the subgraphs G[x] and
H[y] induced by leaves of subtrees of TG and TH rooted at x and y are isomorphic.
For the leaves it is trivial to store such information. Let u and v be two internal
nodes in the modular decomposition trees of TG and TH in the same level. To
decide if G[u] and H[v] are isomorphic A does the following.
If u and v are both series nodes then it just checks if the children of u and
v can be isomorphically matched. The case for parallel node is similar. If u and
v are prime nodes then the vertices of representative graphs Gu and Hv are
colored by their isomorphism type i.e., two internal vertices u1 and u2 of the
representative graphs will get the same color iff subgraphs induced by leaves of
subtrees of TG (or TH ) rooted at u1 and u2 are isomorphic. To test G[u] ∼
= H[v],
bu , H
b v ), where G
b u and H
b v are the colored copies of Gu and Hv
A calls A0 (G
respectively. At any level if we can not find a pairwise isomorphism matching
between the internal nodes in that level of TG and TH then G ∼
= H. In this
manner we make O(n2 ) calls to algorithm A0 at each level. The total runtime of
the algorithm is O(n3 )T (n), where T (n) is run time of A0 . Note that by Lemma
1 clique-width of Gu and Hv are at most k.
t
u

4

Testing Isomorphism between Parse Trees

In this section we define a notion of equivalence of parse trees called structural
isomorphism, and we give an algorithm to test if two given parse trees are equivalent under this notion. As we will see, the graphs generated by equivalent parse
trees are always isomorphic. Thus, if we have two equivalent parse trees for the
two input graphs, the isomorphism problem indeed admits a polynomial time
algorithm. In Section 6, we prove that the CHLRR algorithm can be tweaked
slightly to produce structurally isomorphic parse trees for isomorphic graphs
with clique-width at most three and thus giving a polynomial-time algorithm
for such graphs.
Let G and H be two colored graphs. A bijective map π : V (G) → V (H)
is color consistent if for all vertices u and v of G, color(u) = color(v) iff
color(π(u)) = color(π(v)). Let π : V (G) → V (H) be a color consistent mapping, define π/color : color(G) → color(H) as follows: for all c in color(G),
π/color(c) = color(π(v)) where color(v) = c. It is not hard to see that the map
π/color is well defined. Recall that the internal nodes of a parse tree are ηi,j ,
ρi→j and ⊕ operations. The levels of a parse tree correspond to ⊕ nodes. Let
Tg be a parse tree of G rooted at ⊕ node g. Let g1 be descendant of g which is
neither η nor ρ. We say that g1 is an immediate significant descendant of g if
there is no other ⊕ node in the path from g to g1 . For an immediate significant
descendant g1 of g, we construct a colored quotient graph Qg1 that corresponds
to graph operations appearing in the path from g to g1 performed on graph Gg1 ,
where Gg1 is graph generated by parse tree Tg1 . The vertices of Qg1 are labels of
5

Gg1 . The colors and the edges of Qg1 are determined by the operations on the
path from g1 to g. We start with coloring a vertex a by color a and no edges. If
the operation performed is ηa,b on Gg1 then add edges between vertices of color
a and color b. If the operation is ρa→b on Gg1 then recolor the vertices of color a
with color b. After taking care of an operation we move to the next operation on
the path from g1 to g until we reach ⊕ node g. Notice that if the total number
of labels used in a parse tree is k then the size of any colored quotient graph is
at most k.
Definition 2. Let Tg and Th be two parse trees of G and H rooted at ⊕ nodes
g and h respectively. We say that Tg and Th are structurally isomorphic via a
label map π (denoted Tg ∼
=π Th )
1. If Tg and Th are single nodes2 or inductively,
2. If Tg and Th are rooted at g and h having immediate significant descendants
g1 , · · · , gr and h1 , · · · , hr , and there is a bijection γ : [r] → [r] and for each
i there is a πi ∈ ISO(Qgi , Qhγ(i) ) such that Tgi ∼
=πi Thγ(i) and πi /color =
π|color(Qgi ) , where Tg1 , · · · , Tgr and Th1 , · · · , Thr are the subtrees rooted at
g1 , · · · , gr and h1 , · · · , hr respectively3
We say that Tg and Th are structurally isomorphic if there is a π such that
Tg ∼
=π Th .
The structural isomorphism is an equivalence relation: reflexive and symmetric
properties are immediate from the above definition. The following lemma shows
that it is also transitive.
Lemma 2. Let Tg1 , Tg2 and Tg3 be the parse trees of G1 , G2 and G3 respectively
such that Tg1 ∼
=π1 Tg2 and Tg2 ∼
=π2 Tg3 then Tg1 ∼
=π2 π1 Tg3 .
Proof. The proof is by induction on the height of the parse trees. The base
case trivially satisfies the transitive property. Assume that g1 , g2 and g3 are
nodes of height d + 1. Let g1i be an immediate significant descendant of g1 .
Since Tg1 ∼
=π1 Tg2 , there is an immediate significant descendant g2j of g2 and
π1i ∈ ISO(Qg1i , Qg2j ) such that π1i /color = π|color(Qg1i ) and Tg1i ∼
=π1i Tg2j .
Similarly, g2j will be matched to some immediate significant descendant g3k of
g3 via π2j ∈ ISO(Qg2j , Qg3k ) such that π2j /color = π|color(Qg2j ) and Tg2j ∼
=π2j
Tg3k . The nodes g1i , g2j and g3k has height at most d. Therefore, by induction
hypothesis Tg1i ∼
=π2j π1i Tg3k . By transitivity of isomorphism we can say π2j π1i ∈
ISO(Qg1i , Qg3k ). To complete the proof we just need to show π2j π1i /color =
π2 π1 |color(Qg1i ) . This can be inferred from the following two facts:
1) π2j π1i /color = π2j /color π1i /color
2) π2 π1 |color(Qg1i ) = π2 |color(Qg2j ) π1 |color(Qg1i ) .
t
u
2
3

In this case they are trivially structurally isomorphic via π.
Notice that this definition implies that Ggi and Hhγ(i) are isomorphic via the label
map πi where Ggi and Hhγ(i) are graphs generated by the parse trees Tgi and Thγ(i)
respectively.

6

Algorithm to Test Structural Isomorphism: Next we describe an algorithm that given two parse trees TG and TH tests if they are structurally isomorphic. From the definition if TG ∼
=π TH then we can conclude that G and H are
isomorphic. We design a dynamic programming algorithm that basically checks
the local conditions 1 and 2 in Definition 2.
The algorithm starts from the leaves of parse trees and proceeds in levels
where each level corresponds to ⊕ operations of parse trees. Let g and h denotes
the ⊕ nodes at level l of TG and TH respectively. At each level l, for each pair of
⊕ nodes (g, h) ∈ (TG , TH ), the algorithm computes the set Rlg,h of all bijections
π : lab(Gg ) → lab(Hh ) such that Gg ∼
=πf Hh for some f , and stores in a table
indexed by (l, g, h), where Gg and Hh are graphs generated by sub parse trees Tg
and Th rooted at g and h respectively. To compute Rlg,h , the algorithm uses the
gi ,hj
already computed information Rl+1
where gi and hj are immediate significant
descendants of g and h.
The base case correspond to finding Rlg,h for all pairs (g, h) such that g and
h are leaves. Since in this case Gg and Hh are just single vertices, it is easy to
find Rlg,h . For the inductive step let g1 , · · · , gr and h1 , · · · , hr0 be the immediate
significant descendants of g and h respectively. If r 6= r0 then Rlg,h = ∅. Otherwise
we compute Rlg,h for each pair (g, h) at level l with help of the already computed
information up to level l + 1 as follows.
For each π : lab(Gg ) → lab(Hh ) and pick g1 and try to find a hi1 such
g1 ,hi
that Tg1 ∼
=π1 Thi1 for some π1 ∈ ISO(Qg1 , Qhi1 ) ∩ Rl+1 1 such that π1 /color =
π|color(Qg1 ) . We do this process to pair g2 with some unmatched hi2 . Continue in
this way until all immediate significant descendants are matched. By Lemma 3,
we know that this greedy matching satisfies the conditions of Definition 2. If all
the immediate significant descendants are matched we add π to Rlg,h . It is easy
g,h
to see that if Rlg,h 6= ∅ then the subgraphs Gg ∼
=πf Hh for π ∈ Rl . From the
definition of structurally isomorphic parse trees it is clear that if R0g,h 6= ∅ then
G∼
= H. The algorithm is polynomial time as the number of choices for π and
π1 is at most k! which is a constant, where |lab(G)| = k.
Note that for colored graphs, by ensuring that we only match vertices of
same color in the base case, the whole algorithm can be made to work for colored
graphs. In Lemma 2 we prove that structural isomorphism satisfies transitivity.
In fact, structural isomorphism satisfies a stronger notion of transitivity as stated
in the following lemma.
Lemma 3. Let Tg and Th be two parse trees of graphs G and H. Let g1 and g2
be two immediate significant descendants of g, and h1 and h2 be two immediate
significant descendants of h. Suppose for i = 1, 2, Tgi ∼
=πi Thi for some πi ∈
ISO(Qgi , Qhi ) with πi /color = π|color(Qgi ) . Also assume that Tg1 ∼
=π3 Th2 where
−1
∼π1 π3 π2 Th where
π3 ∈ ISO(Qg , Qh ) and π3 /color = π|color(Q ) . Then, Tg =
1

2

g1

2

π1 π3−1 π2 ∈ ISO(Qg2 , Qh1 ) and π1 π3−1 π2 /color = π|color(Qg2 ) .

1

−1
Proof. By Lemma 2, Tg2 ∼
=π1 π3 π2 Th1 . The rest of the proof is similar to the
proof of the inductive case of Lemma 2.
t
u

7

5

Overview of the CHLRR Algorithm

Corneil et al. [6] gave the first polynomial time algorithm (the CHLRR algorithm), to recognize graphs of clique-width at most three. We give a brief description of their algorithm in this section. We mention that our description of
this fairly involved algorithm is far from being complete. The reader is encouraged to see [6] for details. By Lemma 1 we assume that the input graph G is
prime.
To test whether clique-width of prime graph G is at most three the algorithm
starts by constructing a set of bilabelings and trilabelings of G. In general the
number of bilabelings and trilabelings are exponential, but it was shown (Lemma
8 and 9 in [6] ) that it is enough to consider the following linear size subset
denoted by LabG.
1. For each vertex v in V (G)
[B1] Generate the bilabeling4 {v} and add it to LabG.
[B2] Generate the bilabeling {x ∈ N (v) | N [x] ⊆ N [v]} and add it to LabG.
2. Compute the skeleton of G search this skeleton for the special edges, clique
and star components.
[T1] For each special edge s (corresponds to a proper split), generate the
trilabeling X̃, Ỹ , V (G) \ (X̃ ∪ Ỹ ) where (X,Y ) is the split defined by s
and add it to LabG.
[B3] For all clique components C, generate the bilabeling C and add it to
LabG.
[B4] For all star components S, generate the bilabeling {c}, where c is the
special center of S, and add it to LabG.
Lemma 4. [6] Let G be a prime graph. Clique-width of G is at most three if
and only if at least one of the bilabelings or trilabelings in LabG has clique-width
at most three.
By Lemma 4 the problem of testing whether G is of clique-width at most three
is reduced to checking one of labeled graph in LabG is of clique-width at most
three. To test if a labeled graph A taken from LabG is of clique-width at most
three, the algorithm follows a top down approach by iterating over all possible
last operations that arise in the parse tree representation of G. For example, for
each vertex x in G the algorithm checks whether the last operation must have
joined x with its neighborhood. In this case the problem of testing whether G
can be constructed using at most three labels is reduced to test whether G \ {x}
can be constructed using at most three lables. Once the last operations are fixed
the original graph decomposes into smaller components, which can be further
decomposed recursively.
For each A in LabG, depending on whether it is bilabeled or trilabeled the
algorithm makes different tests on A to determine whether A is of clique-width
4

bilabeling of a set X ⊆ V indicates that all the vertices in X are labeled with one
label and V \ X is labeled with another label.

8

at most three. Based on the test results the algorithm either concludes cliquewidth of A is more than three or returns top operations of the parse tree for
A along with some connected components of A which are further decomposed
recursively.
If A in LabG is connected, trilabeled (with labels l1 , l2 , l3 ) and l-prime then
by the construction of LabG, A corresponds to a split (possibly trivial). If A has a
proper split then there exists a 6= b in {l1 , l2 , l3 } such that A will be disconnected
with the removal of edges Eab . This gives a decomposition with top operations
ηa,b followed by a ⊕ node whose children are connected components of A \ Eab .
If A has a universal vertex v (trivial split) labeled a in A then by removing edges
Eab and Eac we get a decomposition with top operations ηa,b and ηa,c followed
by a ⊕ operation with children connected components of A \ (Eab ∪ Eac ) .
To describe the bilabeled case we use Vi to denote the set of vertices of A
with label i. If A in LabG is connected, bilabeled (with labels l1 , l2 ) and l-prime,
then the last operation is neither ηl1 ,l2 (otherwise A will have a l-module) nor ⊕
(A is connected). So the last operation of the decomposition must be a relabeling
followed by a join operation i.e., we have to introduce a third label set Vl3 such
that all the edges are present between the two of three labeled sets.
After introducing third label if there is only one join to undo, then we have a
unique way to decompose the graph into smaller components. If there are more
than one possible join to be removed, then it is enough to consider one of them
and proceed (see Section 5.2 in [6]). There are four ways to introduce the third
label to decompose the graph, but they might correspond to overlapping cases.
To overcome this the algorithm first checks whether A belongs to any of three
simpler cases described below.
PC1: A has a universal vertex x of label l ∈ {l1 , l2 }. In this case relabel vertex
x with l3 and remove the edges El3 l2 , and El3 l1 to decompose A. This gives a
decomposition with ρl3 →l , ηl3 ,l2 , ηl3 ,l1 followed by ⊕ operation with children x
and A \ {x}.
PC2: A has a vertex x of label l ∈ {l1 , l2 } that is universal to all vertices
of label l0 ∈ {l1 , l2 }, but is not adjacent to all vertices with the other label, say
l¯0 . In this case relabel vertex x with l3 and remove the edges El3 l0 . This gives a
decomposition with ρl3 →l , ηl3 ,l0 above a ⊕ operation with children x and A\{x}.
PC3: A has two vertices x and y of label l, where y is universal to everything
other than x, and x is universal to all vertices of label l other than y, and nonadjacent to all vertices with the other label ¯l. In this case the algorithm relabels
vertices x and y with l3 , and by removing edges El3 l disconnects the graph A,
with two connected components x and A \ {x}. Now in graph A \ {x} again
remove the edges El3 l̄ to decompose the graph into two parts y and A \ {x, y}.
If A does not belongs to any of above three simpler cases then there are
four different ways to introduce the third label set to decompose the graph as
described below.
Let E be the set of all connected, bilabeled, l-prime graphs with clique-width
at most three and not belonging to above three simpler cases. For l ∈ {1, 2} we
define the following four subsets of E.
9

1. Ul : Vla 6= ∅ and removing the edges between the Vla and Vl̄ disconnects the
graph.
2. Dl : V l is not connected and removing the edges between the coconnected
components of V l disconnects the graph.
In these four cases the algorithm introduces a new label l3 and removes the edges
Ell3 , l ∈ {l1 , l2 } to disconnect A. This gives a decomposition with ρl3 →l and ηl,l3
followed by ⊕ operation with children that are the connected components of
A \ Ell3 . For more details about decomposition process when A is in Ul or Dl ,
l ∈ {1, 2} the reader is encouraged to see Section 5.2 in [6].
The following Lemma shows that there is no other possible way of decomposing a clique-width at most three graphs apart from the cases described above.
Lemma 5. [6] E = U1 ∪ U2 ∪ D1 ∪ D2 , and this union is disjoint.
In summary, for any labeled graph A in LabG the CHLRR algorithm tests
whether A belongs to any of the above described cases, if it is then it outputs
suitable top operations and connected components. The algorithm continues the
above process repeatedly on each connected component of A until it either returns a parse tree or concludes clique-width of A is more than three.

6

Isomorphism Algorithm for Prime Graphs of
Clique-width at most Three

In Section 4 we described algorithm to test structural isomporphism between
two parse trees. In this Section we show that given two isomorphic prime graphs
G and H of clique-width at most three, the CHLRR algorithm can be slightly
modified to get structurally isomorphic parse trees. We have used four labels in
order to preserve structural isomorphism in the modified algorithm. The modified
algorithm is presented in Appendix. Recall that the first step of the CHLRR
algorithm is to construct a set LabG of bilabelings and trilabelings of G as
described in Section 5.
Definition 3. We say that LabG is equivalent to LabH denoted as LabG ≡
LabH if there is a bijection g : LabG → LabH such that for all A ∈ LabG, there
is an isomorphism f : V (A) → V (g(A)) and a bijection π : lab(A) → lab(g(A))
such that A ∼
=πf g(A).
Lemma 6. LabG ≡ LabH iff G ∼
=f H.
Proof. The proof follows from the construction of sets LabG and LabH from
input prime graphs G and H and it is presented in Appendix.
t
u
∼π B for some f and π then
Lemma 7. Let A ∈ LabG and B ∈ LabH. If A =
f
parse trees generated from Decompose function (Algorithm 2) for input graphs A
and B are structurally isomorphic. More specifically, Decompose(A) ∼
=πf Decompose(B).
10

Proof. Follows from Lemma 11 and Lemma 12 described in Appendix. The major
modifications are done in PC2 case, where we have used four labels in order to
preserve structural isomorphism between parse trees.
t
u
Isomorphism Algorithm
For two input prime graphs G and H the algorithm works as follows. Using
modified CHLRR algorithm, first a parse tree TG of clique-width at most three
is computed for G. The parse tree TG of G is not canonical but from Lemma 6
and 7, we know that if G ∼
= H then there exists parse tree TH of H, structurally
isomorphic to TG . Therefore we compute parse tree of clique-width at most three
for each labeled graph in LabH. For each such parse tree TH , the algorithm uses
the structural isomorphic algorithm described in Section 4 to test the structural
isomorphism between parse trees TG and TH . If TG ∼
= TH for some TH , then
we conclude that G ∼
= H. If there is no parse tree of H which is structurally
isomorphic to TG then G and H can not be isomorphic.
Computing a parse tree TG of G takes O(n2 m) time. As there are O(n) many
labeled graphs in LabH, computing all possible parse trees for labeled graphs
in LabH takes O(n3 m) time. Testing structural isomorphism between two parse
trees need O(n3 ) time. Therefore the running time to check isomorphism between
two prime graphs G and H of clique-width at most three is O(n3 m).
t
u
The correctness of the algorithm follows from Lemma 8 and Theorem 3.
Lemma 8 shows that if G ∼
= H then we can always find two structurally isomorphic parse trees TG and TH using the modified CHLRR algorithm.
Lemma 8. Let G and H be prime graphs with clique-width at most three. If
G∼
=f H then for every TG in parseG there is a TH in parseH such that TG
is structurally isomorphic to TH where parseG and parseH are the set of parse
trees generated by Algorithm 1 on input LabG and LabH respectively.
Proof. If G ∼
=f H then from Lemma 6 we have LabG ≡ LabH i.e., for every A
in LabG there is a B = g(A) in LabH such that A ∼
=πf B for some f and π. On
input such A and B to Lemma 7 we get two parse trees TA and TB which are
structurally isomorphic.
t
u
Theorem 3. Let G and H be graphs with clique-width at most three. Then there
exists a polynomial time algorithm to check whether G ∼
= H.
Proof. The proof follows from the prime graph isomorphism of graphs with
clique-width at most three described in Lemma 8 and Theorem 2.
t
u

References
1. Babai, L.: Moderately exponential bound for graph isomorphism. In: Fundamentals
of Computation Theory. pp. 34–50. Springer (1981)
2. Babai, L.: Graph isomorphism in quasipolynomial time. arXiv preprint
arXiv:1512.03547 (2015)
3. Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic
index on partial k-trees. Journal of Algorithms 11(4), 631–643 (1990)

11

4. Bonamy, M.: A small report on graph and tree isomorphism.
http://bit.ly/1ySeNBn (2010)
5. Boppana, R.B., Hastad, J., Zachos, S.: Does co-NP have short interactive proofs?
Information Processing Letters 25(2), 127–132 (1987)
6. Corneil, D.G., Habib, M., Lanlignel, J.M., Reed, B., Rotics, U.: Polynomial-time
recognition of clique-width 3 graphs. Discrete Applied Mathematics 160(6), 834–
865 (2012)
7. Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. Journal of computer and system sciences 46(2), 218–270 (1993)
8. Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems 33(2),
125–150 (2000)
9. Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete
Applied Mathematics 101(1), 77–114 (2000)
10. Cournier, A., Habib, M.: A new linear algorithm for modular decomposition. In:
Trees in Algebra and Programming CAAP’94, pp. 68–84. Springer (1994)
11. Cunningham, W.H.: A combinatorial decomposition theory. Canadian Journal of
Mathematics 32(3), 734–765 (1980)
12. Cunningham, W.H.: Decomposition of directed graphs. SIAM Journal on Algebraic
Discrete Methods 3(2), 214–228 (1982)
13. Das, B., Enduri, M.K., Reddy, I.V.: Logspace and fpt algorithms for graph isomorphism for subclasses of bounded tree-width graphs. In: WALCOM: Algorithms
and Computation, pp. 329–334. Springer (2015)
14. Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NPcomplete. SIAM Journal on Discrete Mathematics 23(2), 909–939 (2009)
15. Gallai, T.: Transitiv orientierbare graphen. Acta Mathematica Hungarica 18(1),
25–66 (1967)
16. Grohe, M., Schweitzer, P.: Isomorphism testing for graphs of bounded rank width.
In: Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium
on. pp. 1010–1029. IEEE (2015)
17. James, L.O., Stanton, R.G., Cowan, D.D.: Graph decomposition for undirected
graphs. In: Proceedings of 3rd Southeastern Conference on Combinatorics, Graph
Theory, and Computing. pp. 281–290 (1972)
18. Kamiński, M., Lozin, V.V., Milanič, M.: Recent developments on graphs of
bounded clique-width. Discrete Applied Mathematics 157(12), 2747–2761 (2009)
19. Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Fixed-parameter
tractable canonization and isomorphism test for graphs of bounded treewidth. In:
(FOCS), IEEE 55th Annual Symposium on. pp. 186–195 (2014)
20. Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial
time. Journal of Computer and System Sciences 25(1), 42–65 (1982)
21. Ma, T.H., Spinrad, J.: An O(n2 ) algorithm for undirected split decomposition.
Journal of Algorithms 16(1), 145–160 (1994)
22. Miller, G.: Isomorphism testing for graphs of bounded genus. In: Proceedings of
12th annual ACM symposium on Theory of computing. pp. 225–235. ACM (1980)
23. Oum, S.i., Seymour, P.: Approximating clique-width and branch-width. Journal of
Combinatorial Theory, Series B 96(4), 514–528 (2006)
24. Tedder, M., Corneil, D., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Automata, Languages and
Programming, pp. 634–645. Springer (2008)
25. Zemlyachenko, V., Konieko, N., Tyshkevich, R.: Graph isomorphism problem (russian). In: The Theory of Computation I, Notes Sci. Sem. LOMI 118 (1982)

12

Appendix
7

Graph Isomorphism Completeness for Prime Graphs

For each vertex v ∈ V (G), the polynomial-time many-one reduction adds a new
b After the
vertex v 0 and adds an edge between v and v 0 to get a new graph G.
addition of vertices and edges to the graph it is easy to see that each old vertex
in the graph is adjacent to exactly one vertex of degree one. It is not hard to see
that if M is a non-trivial module in a graph then no vertex in M is adjacent to
b is prime graph.
a vertex of degree one. Thus, we can conclude that G
b1 ∼
b2 .
Lemma 9. Given two connected graphs G1 and G2 , G1 ∼
= G2 iff G
=G
b 1 and G
b 2 are graphs obtained after adding new vertices to G1 and
Proof. Let G
b 1 and
G2 respectively. If G1 ∼
=f G2 then we can find an isomorphism between G
b 2 by extending f to newly added vertices such that for every new vertex y ∈ G
b1
G
having neighbor x, f maps y to z, where z is the newly added neighbor of f (x)
b 2 , as there are no old vertices of
b 2 . For the other direction when G
b1 ∼
in G
=f G
b
b
b 1 to G
b 2 must map the old
degree one in G1 and G2 any isomorphism f from G
b
b
vertices of G1 to the old vertices of G2 . The restriction of f to the old vertices
b 1 and G
b 2 is an isomorphism from G1 to G2 .
of G
t
u
Lemma 10. LabG ≡ LabH iff G ∼
=f H.
Proof. It is easy to see that if LabG ≡ LabH then G ∼
=f H from the definition.
For the other direction, given two graphs G and H isomorphic via f , we need
to prove that there is a bijection g : LabG → LabH such that for all A ∈ LabG,
there is an isomorphism f : V (A) → V (g(A)) and a bijection π : lab(A) →
lab(g(A)) such that A ∼
=πf g(A).
The proof is divided into five cases based on how bilabelings and trilabelings
are generated by CHLRR algorithm described in Section 5.
1. Let A ∈ LabG be generated at B1 in CHLRR algorithm. Therefore, A has
bilabeling {v}. Since G ∼
=f H, there is a graph B ∈ LabH which has bilabeling {f (v)}. Define g(A) = B and a bijection π : lab(A) → lab(B) such that
if lab(v) = i then π(i) = lab(f (v)) so that A ∼
=πf B.
2. Let A ∈ LabG be generated at B2 . Thus, A has bilabeling P = {x ∈
N (v)|N [x] ⊆ N [v]}. As G ∼
=f H, there is a graph B ∈ LabH with bilabeling f (P ) = {f (x) ∈ N (f (v))|N [f (x)] ⊆ N [f (v)]}. Define g(A) = B and
a bijection π : lab(A) → lab(B) such that if lab(P ) = i then π(i) = lab(f (P ))
so that A ∼
=πf B.
3. Let A ∈ LabG be generated at T1 for a special edge s in the skeleton of
G with trilabeling X̃, Ỹ , V (G) \ (X̃ ∪ Ỹ ). As G ∼
=f H and the skeleton
of graph is unique (from Theorem 1), we can find a B ∈ LabH which is
generated for the special edge f (s) in skeleton of H which corresponds to
trilabeling f (X̃), f (Ỹ ), V (H) \ (f (X̃ ∪ Ỹ )). Define g(A) = B and a bijection
π : lab(A) → lab(B) such that if lab(X̃) = i1 then π(i1 ) = lab(f (X̃)), if
13

lab(Ỹ ) = i2 then π(i2 ) = lab(f (Ỹ )), and if lab(V (G) \ (X̃ ∪ Ỹ )) = i3 then
π(i3 ) = lab(V (H) \ (f (X̃ ∪ Ỹ ))) so that A ∼
=πf B.
4. Let A ∈ LabG be generated at B3 for a clique component C with bilabeling C. As G ∼
=f H, there is a B ∈ LabH which is generated for a clique
component f (C) with bilabeling f (C). Define g(A) = B and a bijection
π : lab(A) → lab(B) such that if lab(C) = i then π(i) = lab(f (C)) so that
A∼
=πf B.
5. Let A ∈ LabG be generated at B4 for a star component S with bilabeling {c},
where c is a special center of S. As G ∼
=f H, there is a graph B ∈ LabH which
is generated for a star component f (S) with bilabeling f (c), where f (c) is a
special center of f (S). Define g(A) = B and a bijection π : lab(A) → lab(B)
such that if lab(c) = i then π(i) = lab(f (c)) so that A ∼
t
u
=πf B.

8

Generating Structurally Isomorphic Parse Trees

In this section we prove that the modified CHLRR algorithm generates structurally isomorphic parse trees on two isomorphic input graphs. To prove that we
also show that the supporting subroutines do the same.
Algorithm 1: Finding parse trees for labeled graphs of clique-width at
most three in LabG

1
2
3
4
5
6
7
8

Input: LabG a set of bilabelings and trilabelings of G
Output: parseG = {TA | TA is a parse tree of graph A in LabG of clique-width at most
three }
begin
parseG := ∅
for all A ∈ LabG do
A.parse-tree := null
A.parse-tree = Decompose(A)
if A.parse-tree 6= null then
Add A.parse-tree to parseG
return (parseG)

The function Decompose(P ) in Algorithm 1 finds parse tree of P if cwd(P ) ≤
3 and it is described in following Section and Appendix.

8.1

Decomposing Trilabeled Graphs

The function Decompose-leaf -T I (Algorithm 3) decomposes trilabeled graph
from LabG. It can be check that this function is always called with inputs coming
from LabG. In other words it is only called in the first level of the recursion.
Lemma 11. Let A in LabG and B in LabH be trilabeled and l-prime connected
graphs. If A ∼
=πf B for some f and π then Algorithm 3 generates top operations
of parse trees for A and B such that π ∈ ISO(Qa , Qb ) with Aa ∼
=πf Bb , where Aa
and Bb are the graphs described in Algorithm 3.
Proof. Let A and B are trilabeled with l1 , l2 , l3 and l10 , l20 , l30 respectively. If A has
a trivial split (see Figure 1) then it has a universal vertex x of some label l1 . Then
14

Algorithm 2: Function Decompose [6]
1
2

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Input: A bi or trilabled l-prime connected graph P
Output: A parse tree of P or null parse tree if cwd(P ) > 3
begin
parse-tree := a trivial parse tree with P as the unique leaf
/* parse-tree may contain connected components as leafs but as the algorithm proceeds
this components will be decomposed to finally obtain the parse tree
*/
Leaves := {P }
/* Leaves contains pointer to P */
while Leaves 6= ∅ do
flag := true, tree := null
Extract Γ from Leaves
if Γ has no more than three vertices then
Find a canonical parse tree, tree
Replace Γ by tree in parse-tree
if Γ is trilabled then
[flag, tree] = Decompose-leaf-TI(Γ )
Add the leafs of tree to Leaves
Replace Γ by tree in parse-tree
else
[flag, tree] = Decompose-leaf-BI(Γ )
Add the leafs of tree to Leaves
Replace Γ by tree in parse-tree
if flag is false then
parse-tree := null
return (parse-tree)
return (parse-tree)

the algorithm removes the edges El1 l2 , El1 l3 from A and gives a decomposition
with top operations ηl1 ,l2 and ηl1 ,l3 above a ⊕ operation whose children are x and
connected components Aa1 , · · · , Aak (Aa = x⊕Aa1 ⊕· · ·⊕Aak ). If A ∼
=πf B, then
0
there is a universal vertex y in B of label l1 such that f (x) = y and π(l1 ) = l10 .
To decompose B, the algorithm removes the edges El10 l20 , El10 l30 from B to get the
decomposition with top operations ηl10 l20 and ηl10 l30 above a ⊕ operation whose
children are y and connected components Bb1 , · · · , Bbk (Bb = y ⊕ Bb1 ⊕ · · · ⊕
Bbk ). In fact Bb1 , · · · , Bbk are images of Aa1 , · · · , Aak under f in some order.
The quotient graphs Qa and Qb have three vertices corresponding to top two
consecutive η operations. If A ∼
=πf B the quotient graphs are isomorphic via π
π
and Aa ∼
=f Bb .
If A corresponds to a nontrivial split (see Figure 2) then there are two labels
l1 , l2 such that El1 l2 is complete. We get a decomposition with ηl1 ,l2 operation
above a ⊕ operation whose children are connected components Aa1 , · · · , Aak
(Aa = Aa1 ⊕ · · · ⊕ Aak ) of A after the El1 l2 edges are removed. If A ∼
=πf B,
0
0
then there exists a nontrivial split in B and two labels l1 , l2 such that El10 l20
is complete and π{l1 , l2 } = {l10 , l20 }, π(l3 ) = l30 . To decompose B, the algorithm
removes the edges El10 l20 , to get the decomposition with top operations ηl10 ,l20 above
a ⊕ operation whose children are connected components Bb1 , · · · , Bbk obtained
from B after El10 l20 edges are removed. The quotient graphs Qa and Qb build
from the top operations are isomorphic via π and Aa ∼
t
u
=πf Bb .

15

Algorithm 3: Function Decompose-leaf-TI [6]
1
2
3
4

5
6

Input: A trilabeled, l-prime and connected graph G
Output: true with top operations of parse tree or false if cwd(G) > 3
begin
tree := null
if G has a universal vertex x of label l1 then
Let Gg = x ⊕k
i=1 Ggi , where x, Ggi ’s are connected components of
G \ {El1 l2 , El1 l3 }
/* l1 , l2 , l3 are labels of G */
tree = ηl1 ,l2 ηl1 ,l3 (x ⊕k
i=1 Ggi )
return (true, tree)

10

if G has two labels l1 , l2 such that El1 l2 is complete then
Let Gg = ⊕k
i=1 Ggi , where Ggi ’s are connected components of G \ {El1 l2 }
tree = ηl1 ,l2 (⊕k
i=1 Ggi )
return (true, tree)

11

return (false, tree) (i.e., cwd(G) > 3)

7
8
9

Algorithm 4: Function Decompose-leaf -BI (cf., [6])
1
2
3
4
5

6
7
8
9
10
11
12
13
14
15

Input: A bilabeled, l-prime and connected graph G
Output: true with top operations of parse tree or false if cwd(G) > 3
begin
tree := null
if G ∈ PC1 then
if G has a universal vertex (say x) then
Let Gg = x ⊕k
i=1 Ggi , where x, Ggi ’s are connected components of
G \ {El3 l2 , El3 l1 }
/* l1 , l2 are labels of G */
tree = ρl3 →l ηl3 ,l2 ηl3 ,l1 (x ⊕k
i=1 Ggi )
return (true, tree)
if G ∈ PC2 then
Compute a set S number of vertices in G which are universal to one label class but
not adjacent to other label class
if |S| equal to 1(say x) then
Let Gg = x ⊕k
i=1 Ggi , where x, Ggi ’s are connected components of G \ {El3 l0 }
tree = ρl3 →l ηl3 ,l0 (x ⊕k
i=1 Ggi )
return (true, tree)
if |S| equal to 2 (say x1 and x2 ) then
Let Gg = x1 ⊕ x2 ⊕k
i=1 Ggi , where x1 , x2 , Ggi ’s are connected components of
G \ {El3 l0 , El ,l0 }
4

0 ηl ,l0 ρl3 →l0 ηl3 ,l0 (x1
4

16

tree = ρl

17

return (true, tree)

18
19

20
21
22

23
24
25
26
27

4 →l

⊕ x 2 ⊕k
i=1 Ggi )

if G ∈ PC3 then
Let Gg = x ⊕ y ⊕k
i=1 Ggi , where x, y, Ggi ’s are connected components of
G \ {El3 l , El4 ,l̄ }
tree = ρl3 →l ηl3 ,l (x ⊕ ηl3 ,l̄ (y ⊕k
i=1 Ggi ))
return (true, tree)
Compute the coconnected components of Vl1 and Vl2 and test membership of G in
Ul1 , Ul2 , D l1 and D l2
if G ∈ Ul1 then return(Decompose-leaf-Ul1 (G))
if G ∈ Ul2 then return(Decompose-leaf-Ul2 (G))
if G ∈ D l1 then return(Decompose-leaf-D l1 (G))
if G ∈ D l2 then return(Decompose-leaf-D l2 (G))
if G ∈
/ Ul1 , Ul2 , D l1 and D l2 then return(false,tree) (i.e., cwd(G) > 3)

16

ηl1 ,l2
ηl1 ,l3

x(l1 )

⊕
A \ {x}

x(l1 ) A \ {x}

Fig. 1 Trivial split: x is a universal vertex of label l1 in a trilabeled graph A.
We use the bold edge between two sets of vertices to indicate that all edges are
present between two vertex sets.

ηl1 ,l2
Vl3
Aaj+1

Aa1
Aaj

Aak

Vl1

Vl2

⊕
Aa1 · · · Aaj · · · Aak

Fig. 2 Nontrivial split: Vi represents set of vertices in A that have label i.

8.2

Decomposing Bilabeled Graphs

Our modification to the CHLRR algorithm is in Decompose-leaf -BI (Algorithm 4), where we use four labels instead of three to find structural isomorphic
parse trees. If G is a bilabeled, l-prime and connected graph of clique-width
at most three, then either G ∈ P Ci where i ∈ {1, 2, 3} or G ∈ Ui , Di where
i ∈ {1, 2} (See Proposition 29 in [6]). From here on wards we assume that G and
H are bilabeled with l1 , l2 and l10 , l20 respectively.
Lemma 12. Let G and H be bilabeled, l-prime and connected graphs. If G ∼
=πf H
for some f and π then Algorithm 4 generates top operations of parse trees G
and H such that there is a πi ∈ ISO(Qg , Qh ) with Gg ∼
=πf i Hh and πi /color =
π|color(Qg ) , where Gg and Hh are the graphs described in Algorithm 4.
Proof. There are three simple cases that can be handled easily. These simple
cases denoted as PC1, PC2 and PC3. The other cases Ul1 (Ul2 ) and Dl1 (Dl2 )
are described in Algorithms 5 and 6 in Appendix.
1
17

PC1: If G ∈ P C1 then G has a universal vertex of label l ∈ {l1 , l2 } (see
Figure 3). Note that in this case G can not have more than two universal vertices
of same label, otherwise those universal vertices form an l-module.
To decompose G the algorithm relabels vertex x with l3 and removes the
edges El3 l2 and El3 l1 . Then we get the decomposition with ρl3 →l , ηl3 ,l2 , ηl3 ,l1
above a ⊕ operation with children x and connected components Gg1 , · · · , Ggk
(Gg = x ⊕ Gg1 ⊕ · · · ⊕ Ggk ). If G ∼
=πf H then algorithm finds the unique universal
0
0 0
vertex y in H of label l ∈ {l1 , l2 } such that f (x) = y and π(l) = l0 . To decompose
H the algorithm relabels the vertex y with l30 and removes the edges El30 l20 and
El30 l10 to get the decomposition with ρl30 →l0 , ηl30 ,l20 , ηl30 ,l10 above a ⊕ operation
with children y and connected components Hh1 , · · · , Hhk (these are images of
Gg1 , · · · , Ggk under f in some order). The quotient graphs Qg and Qh build from
the top operations are isomorphic via πi , where πi (l3 ) = l30 and πi (l) = π(l) if
l ∈ {l1 , l2 }. It is clear that, Gg ∼
=πf i Hh and πi /color = π|color(Qg ) .

ρl3 →l
ηl3 ,l2
ηl3 ,l1

x(l)

⊕
G \ {x}

x(l3 ) G \ {x}

Fig. 3 PC1: Decomposition of a bilabeled graph G with a universal vertex x.
Suppose G has two universal vertices x1 and x2 of label l1 and l2 respectively.
In this case we apply above procedure consecutively two times first taking x1 as
a universal vertex in graph G, second taking x2 as a universal vertex in graph
G \ {x1 }. Note that the order in which we consider x1 and x2 does not effect the
structure of the parse tree.
PC2: If G ∈ P C2 then G can have one or two vertices of different labels
which are universal to vertices of one label class but not to other label class. Let
l1 and l2 be the labels of G. In this case the algorithm finds the decomposition
of G described as follows:
Case-1: Suppose G has a single vertex x of label l (see Figure 4a) that is
universal to all vertices of label l0 ∈ {l1 , l2 }, but not adjacent to all vertices of
label l¯0 ∈ {l1 , l2 } \ l0 . To decompose G, the algorithm relabels x with a label
l3 ∈
/ {l1 , l2 } and removes the edges El3 l0 , which gives the decomposition with
18

top operations ρl3 →l , ηl3 ,l0 above a ⊕ operation with children x and connected
components Gg1 , · · · , Ggk (Gg = x ⊕ Gg1 ⊕ · · · ⊕ Ggk ). If G ∼
=πf H, the algorithm
finds a vertex y in H of label m which is universal to all vertices of label m0 but
not adjacent to all vertices of label m̄0 such that f (x) = y and π(l) = m. To
decompose H the algorithm relabels y with a label l30 ∈
/ {l10 , l20 } and removes the
edges El30 m , which gives the decomposition with top operations ρl30 m , ηl30 ,m0 above
a ⊕ operation whose children are y and the connected components Hh1 , · · · , Hhk
(these are images of Gg1 , · · · , Ggk under f in some order). The quotient graphs
Qg and Qh build from top operations are isomorphic via πi , where πi (l) = m,
π(¯l) = m̄ and πi (l3 ) = l30 . Moreover, Gg ∼
=πf i Hh and πi /color = π|color(Qg ) .

x1 (l)

ρl4 →l̄
ηl4 ,l̄0

x(l)

ρl3 →l

l0

ηl3 ,l0
l

0

¯l0

⊕
¯l0

ρl3 →l
ηl3 ,l0
⊕

x(l3 ) G \ {x}
x2 (¯l)

(a) PC2: Case 1

x1 (l3 ) x2 (l4 )

G \ {x, y}

(b) PC2: Case 2

Fig. 4 Decomposing a bilabeled graph G, having one or two vertices of different
labels which are universal to vertices of one label class but not to other label
class. We use the zigzag edge to indicate the presence of some edges between the
two sets of vertices

Case-2: Suppose G has two vertices x1 and x2 of label l ∈ {l1 , l2 } (see Figure 4b) and ¯l ∈ {l1 , l2 } \ l such that x1 (x2 ) is universal to all vertices of label
l0 ∈ {l1 , l2 } (¯l0 ), but not adjacent to all vertices of label ¯l0 (l0 ). Then the algorithm relabels vertices x1 and x2 with l3 and l4 respectively and removes edges
El4 ,l̄0 , El3 ,l0 to get the decomposition of G with ρl4 →l̄ , ηl4 ,l̄0 , ρl3 →l , ηl3 ,l0 above
a ⊕ operation with children x1 , x2 and connected components Gg1 , · · · , Ggk
(Gg = x1 ⊕ x2 ⊕ Gg1 ⊕ · · · ⊕ Ggk ). If G ∼
=πf H, the algorithm finds vertices y1 and
0 0
y2 in H of label m ∈ {l1 , l2 } and m̄ ∈ {l10 , l20 } \ m such that y1 (y2 ) is universal
to all vertices of label m0 (m̄0 ), but not adjacent to all the vertices of label m̄0
19

(m0 ) and f (x1 ) = y1 , f (x2 ) = y2 . Then algorithm relabels vertices y1 and y2
with l30 and l40 respectively and removes edges El40 ,m̄0 ,El30 ,m0 to get the decomposition of H with top operations ρl40 →m̄ , ηl40 ,m̄0 , ρl30 →m , ηl30 ,m0 above a ⊕ operation
whose children are y1 , y2 and connected components Hh1 , · · · , Hhk (these are
images of Gg1 , · · · , Ggk under f in some order). The quotient graphs Qg and Qh
build from the top operations are isomorphic via πi , where πi (l0 ) = π(l0 ) = m0 ,
πi (¯l0 ) = π(¯l0 ) = m̄0 , πi (l3 ) = l30 and πi (l4 ) = l40 . It is clear that, Gg ∼
=πf i Hh and
πi /color = π|color(Qg ) .
PC3: If G ∈ P C3 then G has two vertices x and y of label l, where y is
universal to everything other than x, and x is universal to all vertices of label
l other than y, and non-adjacent of all vertices of the other label l as shown in
Figure 5. To decompose G the algorithm relabels the vertices x and y with l3
and removes the edges El3 l to get the decomposition of G with top operations
ρl3 →l , ηl3 ,l and a ⊕ with the connected components of Gg = x ⊕ G \ {x} as
children. Again the algorithm removes the edges El3 l from G \ {x} to get the
decomposition with top operations ηl3 ,l̄ and a ⊕ with the connected components
of Gg1 = y ⊕ G \ {x, y} as children. If G ∼
=πf H, the algorithm finds the vertices
0 0
0
x , y ∈ H of label l such that f (x) = x0 , f (y) = y 0 and π(l) = l0 . where y 0 is
universal to everything other than x0 , and x0 is universal to all vertices of label
0
l0 other than y 0 , and non-adjacent to all vertices of label l . Then it relabels
vertices x0 and y 0 with l30 and removes the edges El30 l0 to get the decomposition
of H with top operations ρl30 →l0 , ηl30 ,l0 and a ⊕ with the connected components
of Hh = x0 ⊕ H \ {x0 } as children. Again the algorithm removes the edges El30 ,l̄0
from H \ {x0 } to get the decomposition with top operations ηl30 ,l̄0 and a ⊕ with
the connected components of Hh1 = y 0 ⊕ H \ {x0 , y 0 } as children. In this case the
generated parse tree has two levels.
In first level the quotient graphs Qg and Qh build from top operations are
isomorphic via π1i , where π1i (l) = π(l) if l ∈ {l1 , l2 }, π1i (l3 ) = l30 . It is clear that,
Gg ∼
=fπ1i Hh and π1i /color = π|color(Qg ) . In second level the quotient graphs Qg1
and Qh1 build from top operations are isomorphic via π2i , where π2i (l) = π1i (l)
if l ∈ {l1 , l2 , l3 }, and Gg1 ∼
=πf 2i Hh1 , π2i /color = π1i |color(Qg1 ) . The remaining
part of proof follows from Lemma 13 and 14.
t
u
8.3

Function Decompose Ul1 :

We next describe the case Ul1 . The case Ul2 is omitted from here because it is
similar to Ul1 . Let l1 and l2 be the vertex labels. The vertex set Vl1 consisting of
vertices with label l1 can be partitioned as follows: The set of vertices adjacent to
all vertices of Vl2 is denoted Vla1 . The set of vertices adjacent to some of vertices
of Vl2 is denoted Vls1 . The set of vertices adjacent to none of vertices of Vl2 is
denoted Vln1 . Similarly we can define the sets Vla2 , Vls2 and Vln2 . For l ∈ {l1 , l2 } we
say, G ∈ Ul if Vla 6= ∅ and removing the edges between Vla and Vl disconnects
G.
Lemma 13. Let G and H be bilabeled, l-prime and connected graphs. If G ∼
=πf H
for some f and π then Algorithm 5 generates top operations of parse trees G
20

ρl3 →l
ηl3 ,l
⊕
ηl3 ,l̄
y(l)

x(l3 )

⊕

x(l)

l

G \ {x, y}

y(l3 )

¯l

Fig. 5 Decomposing a bilabeled graph G which has two vertices x and y of
label l, where y is universal to everything other than x, and x is universal to
all vertices of label l other than y, and non-adjacent of all vertices of the other
label ¯l

and H such that there is a πi ∈ ISO(Qg , Qh ) with Gg ∼
=πf i Hh and πi /color =
π|color(Qg ) , where Gg and Hh are the graphs described in Algorithm 5.
Proof. G ∈ Ul1 if Vla1 6= ∅ and removing the edges between Vla1 and Vl2 disconnects
G. The proof is divided into two cases based on connected components (partial5
and non partial) of V1 .
5

A connected component of V1 that contains at least one vertex of V1s is called partial.

Algorithm 5: Function Decompose-leaf -Ul1 [6]
1
2
3
4
5
6

Input: A bilabeled, l-prime and connected graph G
Output: true with top operations of parse tree or false if cwd(G) > 3
begin
tree := null
if G has good non partial connected component C then
Let Gg = ⊕k
i=1 Ggi , where Ggi ’s are connected components of G \ {El3 ,l2 }
tree = ρl3 →l1 ηl3 ,l2 (⊕k
i=1 Ggi )
return (true, tree)

10

if G has only partial connected components then
Let Gg = ⊕k
i=1 Ggi , where Ggi ’s are connected components of G \ {El3 ,l2 }
tree = ρl3 →l1 ηl3 ,l2 (⊕k
i=1 Ggi )
return (true, tree)

11

return (false, tree) (i.e., cwd(G) > 3)

7
8
9

1

21

If there is at least one good connected component 6 C (see Section 5.2.1 in
[6]) in G then the algorithm relabels all vertices of Vla1 in good connected components with l3 and removes the edges El3 l2 from G to get the decomposition
with top operations ρl3 →l1 and ηl3 ,l2 above a ⊕ operation with the connected
components Gg1 , · · · , Ggk as children (Gg = Gg1 ⊕ · · · ⊕ Ggk ). If G ∼
=πf H, up
to a permutation of labels H may be in Ul10 or Ul20 , but this does not effect the
structure of the decomposition as in both the cases the set of edges deleted are
same. The algorithm finds at least one good connected component C 0 in H and
relabels all vertices of Vla0 in good connected components with l30 and removes
1
the edges El30 l20 from H to get the decomposition with top operations ρl30 →l10 and
ηl30 ,l20 above a ⊕ operation with connected components Hh1 , · · · , Hhk as children
(these are images of Gg1 , · · · , Ggk under f in some order). The quotient graphs
Qg and Qh build from top operations are isomorphic via πi , where πi (l) = π(l)
if l ∈ {l1 , l2 }, πi (l3 ) = l30 . It is clear that, Gg ∼
=πf i Hh and πi /color = π|color(Qg ) .
If there are only partial components 5 (see Section 5.2.1 in [6]) in graph G
then the algorithm relabels all the vertices Vla1 with l3 and removes the edges
El3 l2 from G to get the decomposition with top operations ρl3 →l1 and ηl3 ,l2
above a ⊕ operation with the connected components Gg1 , · · · , Ggk as children
(Gg = Gg1 ⊕ · · · ⊕ Ggk ). If G ∼
=πf H, the algorithm relabels all the vertices Vla10
in H with l30 and removes the edges El30 l20 to get the decomposition with top
operations ρl30 →l10 and ηl30 ,l20 above a ⊕ operation with the connected components
Hh1 , · · · , Hhk as children (these are images of Gg1 , · · · , Ggk under f in some
order). The quotient graphs Qg and Qh build from top operations are isomorphic
via πi , where πi (l) = π(l) if l ∈ {l1 , l2 }, πi (l3 ) = l30 , and Gg ∼
=πf i Hh , πi /color =
π|color(Qg ) .
Lemma 30, 31 in [6] shows that if G ∈ Ul1 apart from above two ways there
is no other way to continue to find the decomposition for graphs of clique-width
at most three.
t
u
8.4

Function Decompose D l1 :

Let Vl be the set of vertices with label l. For l ∈ {l1 , l2 } we say, G ∈ Dl if Vl is
not connected and removing edges between the coconnected components of Vl
disconnects G.
Lemma 14. Let G and H be bilabeled, l-prime and connected graphs. If G ∼
=πf H
for some f and π then Algorithm 6 generates top operations of parse trees G
and H such that there is a πi ∈ ISO(Qg , Qh ) with Gg ∼
=πf i Hh and πi /color =
π|color(Qg ) , where Gg and Hh are the graphs described in Algorithm 6.
Proof. The proof is divided into three cases depending on the structure of the
graph.
6

A non-partial connected component C of V1 is good (respectively, bad), if G is of
clique-width at most three implies that the bilabeled graph obtained from C by
relabeling all the vertices of V1a ∪ C with three is of clique-width at most three
(respectively of clique-width more than three).

22

Algorithm 6: Function Decompose-leaf -Dl1 [6]
1
2
3
4
5
6
7
8
9
10

Input: A bilabeled, l-prime and connected graph G
Output: true with top operations of parse tree or false if cwd(G) > 3
begin
tree := null
if G has only two coconnected components then
Let Gg = ⊕k
i=1 Ggi , where Ggi ’s are connected components of G \ {El3 l1 }
tree = ρl3 →l1 ηl3 ,l1 (⊕k
i=1 Ggi )
return (true, tree)
if G has proper partition then
Let Gg = Gg1 ⊕ Gg2 , where Gg1 and Gg2 are connected components of G \ {El3 l1 }
tree = ρl3 →l1 ηl3 ,l1 (Gg1 ⊕ Gg2 )
return (true, tree)

14

if G is eligible then
Let Gg = y ⊕ (Gg1 \ y) ⊕k
i=2 Ggi , where Ggi ’s are connected components of
G \ {El3 l1 } and y, Gg1 \ y’s are connected components of Gg1 \ {El3 l2 }
tree = ρl3 →l1 ηl3 ,l1 (ηl3 l2 (y ⊕ Gg1 \ y) ⊕k
i=2 Ggi )
return (true, tree)

15

return(false,tree) (i.e., cwd(G) > 3)

11
12

13

If there are only two coconnected components CCC1 and CCC2 of Vl1 , then
the algorithm relabels one of CCC1 or CCC2 at random width l3 and removes
the edges El3 l1 to get the decomposition with top operations ρl3 →l1 and ηl3 ,l1
above a ⊕ operation with the connected components Gg1 , · · · , Ggk as children
(Gg = Gg1 ⊕ · · · ⊕ Ggk ). If G ∼
=πf H, up to a permutation of labels H may be in
Dl10 or (Dl20 ), without loss of generality assume H is in Dl10 . In H the algorithm
relabels one of the coconnected component of Vl10 at random with l30 and removes
the edges El30 l10 to get the decomposition with top operations ρl30 →l10 and ηl30 ,l10
above a ⊕ operation with the connected components Hh1 , · · · , Hhk as children
(these are images of Gg1 , · · · , Ggk under f in some order). The quotient graphs
Qg and Qh build from top operations are isomorphic via πi , where πi (l2 ) = l20 ,
πi (l1 ) = l10 or l30 , πi (l3 ) = l30 or l10 , and Gg ∼
=πf i Hh , πi /color = π|color(Qg ) .
If G has a proper partition 7 then algorithm relabels one side of Vl1 with l3
and removes the edges El3 l1 to get the decomposition with top operations ρl3 →l1
and ηl3 ,l1 above a ⊕ operation with the connected components Gg1 and Gg2
(Gg = Gg1 ⊕ Gg2 ) as children. If G ∼
=πf H, the algorithm relabels one side of Vl10
0
0
0
with l3 and removes the edges El3 l1 to get the decomposition with top operations
ρl30 →l10 and ηl30 ,l10 above a ⊕ operation with the connected components Hh1 and
Hh2 as children. The quotient graphs Qg and Qh build from top operations are
isomorphic via πi , where πi (l2 ) = l20 , πi (l1 ) = l10 or l30 , πi (l3 ) = l30 or l10 , and
Gg ∼
=πf i Hh , πi /color = π|color(Qg ) .
If G is eligible (see Section 5.2.2 in [6] for definition) then to decompose G
the algorithm relabels vertices in coconnected component CCCd with l3 and
7

partition of the coconnected components of Vl1 into two sides such that the vertices
of Vl2 also partitions into two sides but no connected component of Vl2 has vertices
in both sides

23

removes the edges El3 l1 to get the decomposition with top operations ρl3 →l1 ,
ηl3 ,l1 and a ⊕ with the connected components Gg1 , · · · , Ggk as children (Gg =
Gg1 ⊕ · · · ⊕ Ggk ). Again the algorithm removes the edges El3 l2 from Gg1 to
get the decomposition with top operations ηl3 ,l2 and a ⊕ with the connected
components of Gg1 = Gg1 \ {y} ⊕ y as children. If G ∼
=πf H, the algorithm
0
0
relabels coconnected component CCCd with l3 and removes the edges El30 l10
from H to get the decomposition with top operations are ρl30 →l10 , ηl30 ,l10 and a ⊕
with the connected components Hh1 , · · · , Hhk (these are images of Gg1 , · · · , Ggk
under f in some order) as children. Again the algorithm removes the edges El30 ,l20
from Hh1 to get the decomposition with top operations ηl30 ,l20 and a ⊕ with the
connected components of Hh1 = Hh1 \ {y 0 } ⊕ y 0 as children. In this case the
generated parse tree has two levels. In the first level the quotient graphs Qg
and Qh built from top operations are isomorphic via π1i , where π1i (l) = π(l)
if l ∈ {l1 , l2 }, π1i (l3 ) = l30 , and Gg ∼
=πf 1i Hh , π1i /color = π|color(Qg ) . In the
second level the quotient graphs Qg1 and Qh1 built from top operations are
isomorphic via π2i , where π2i (l) = π1i (l) if l ∈ {l1 , l2 , l3 }, and Gg1 ∼
=fπ2i Hh1 ,
π2i /color = π1i |color(Qg1 ) .
Lemma 32 in [6] shows that if G ∈ Dl1 apart from the above three ways there
is no other way to continue to find the decomposition for graphs of clique-width
at most three.
t
u

24

