DIMACS TR: 2004-19

The Relative Clique-Width of a Graph



Authors: Vadim V. Lozin and Dieter Rautenbach

ABSTRACT
The tree-width of graphs is a well-studied notion the importance of which is partly due to the fact that many hard algorithmic problems can be solved efficiently when restricted to graphs of bounded tree-width. The same is true for the clique-width which is a relatively young notion generalizing tree-width in the sense that graphs of bounded tree-width have bounded clique-width.

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 clique-width, 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

DIMACS Home Page