## 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