Whereas tree-decompositions that are used to define tree-width are a very intuitive and easily visualizable way to represent the global structure of a graph, the clique-width is much harder to grasp intuitively. To better understand the nature of the clique-width, we introduce the notion of relative clique-width and study two algorithmical problems related to it. In conjunction, these problems would allow to determine the clique-width.
For one of the problems, which is to determine the relative
we propose a polynomial-time factor 2 approximation algorithm
and also show an exact solution in a natural special case.
The study of the other problem, which is left open in the paper,
has brought us to an alternative and transparent proof
of the known fact that graphs of bounded tree-width
have bounded clique-width.
Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-19.ps.gz