\input zb-basic
\input zb-ioport
\iteman{io-port 05711874}
\itemau{M\"uller, Haiko; Urner, Ruth}
\itemti{On a disparity between relative cliquewidth and relative NLC-width.}
\itemso{Discrete Appl. Math. 158, No. 7, 828-840 (2010).}
\itemab
Summary: Cliquewidth and NLC-width are two closely related parameters that measure the complexity of graphs. Both clique- and NLC-width are defined to be the minimum number of labels required to create a labelled graph by certain terms of operations. Many hard problems on graphs become solvable in polynomial-time if the inputs are restricted to graphs of bounded clique- or NLC-width. Cliquewidth and NLC-width differ at most by a factor of two. The relative counterparts of these parameters are defined to be the minimum number of labels necessary to create a graph while the tree-structure of the term is fixed. We show that Relative Cliquewidth and Relative NLC-width differ significantly in computational complexity. While the former problem is NP-complete the latter is solvable in polynomial time. The relative NLC-width can be computed in $\cal O(n^3)$ time, which also yields an exact algorithm for computing the NLC-width in time $\cal O(3^nn)$. Additionally, our technique enables a combinatorial characterisation of NLC-width that avoids the usual operations on labelled graphs.
\itemrv{~}
\itemcc{}
\itemut{cliquewidth; NLC-width; exact algorithm; characterisation}
\itemli{doi:10.1016/j.dam.2009.06.024}
\end