The relative clique-width of a graph (Q2642017)

Vertex-labelled graphs are represented by terms constructed from constants \(\bullet_i\) (single vertex labelled \(i\)), unary functions \(\rho_{i \to j}\) (relabel) and \(\eta_{i,j}\) (add edges between vertices labelled \(i\) and \(j\)) and the binary function \(\oplus\) (disjoint union). The minimum number of labels used to create \(G\) (with any labelling) is called the clique-width of \(G\) and denoted by \(\text{cwd}(G)\), see \textit{B. Courcelle, J. Engelfriet} and \textit{G. Rozenberg} [J.\ Comput.\ Syst.\ Sci.\ 46, No. 2, 218--270 (1993; Zbl 0825.68446)]. For a graph of clique-width \(k \leq 3\), \textit{Corneil et al.} [Lect.\ Notes Comput. Sci. 1776, 126--134 (2000; Zbl 0961.05062)] showed how to contstruct a certifying term in polynomial time. For \(k > 4\), \textit{M. R. Fellows et al.} [Clique-width minimization is NP-hard (extended abstract), Proc. 38th STOC, 354--362 (2006)] proved that ``\(\text{cwd}(G) \leq k\)?'' is NP-complete to decide. The reduced tree of a term is its parse tree with \(\rho\)- and \(\eta\)-nodes removed (by contracting incident arcs). The clique-width of \(G\) relative to \(T\), denoted by \(\text{cw}(G,T)\), is the minimum number of labels used to create \(G\) via a term with reduced tree \(T\). Obviously, \(\text{cwd}(G) = \min\{\text{cw}(G,T) \mid T \text{\;is a reduced tree}\}\). The authors prove some bounds on \(\text{cw}(G,T)\) and propose an \(O(n^2m)\)-time algorithm approximating \(\text{cw}(G,T)\) by a factor of at most 2.