Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR05-080 | 24th August 2005 00:00

Proving NP-hardness for clique-width I: non-approximability of sequential clique-width

RSS-Feed




Revision #1
Authors: Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider
Accepted on: 24th August 2005 00:00
Downloads: 1390
Keywords: 


Abstract:

Clique-width is a graph parameter, defined by a composition mechanism
for vertex-labeled graphs, which measures in a certain sense the
complexity of a graph. Hard graph problems (e.g., problems
expressible in Monadic Second Order Logic, that includes NP-hard
problems) can be solved efficiently for graphs of certified small
clique-width. It is widely believed that determining the clique-width
of a graph is NP-hard; in spite of considerable efforts, no
NP-hardness proof has been found so far.

In this paper we show a non-approximability result for restricted form
of clique-width, termed r-sequential clique-width, considering only
such clique-width constructions where one of any two graphs put
together by disjoint union must have r or fewer vertices. In
particular, we show that for every positive integer r, the
r-sequential clique-width cannot be absolutely approximated in
polynomial time unless P=NP, and that given G and k the question of
whether the r-sequential clique-width of G is at most k is
NP-complete.

We show further that this non-approximability result holds even for
graphs of a very particular structure: for graphs obtained from
cobipartite graphs by replacing edges with induced paths. In part II
of this series of papers we use this strengthened result to show that,
unless P=NP, there is no polynomial-time absolute approximation
algorithm for (unrestricted) clique-width, and that, given a graph G
and an integer k, deciding whether the the clique-width G is at most k
is NP-complete. This solves a problem that has been open since the
introduction of clique-width in the early 1990s.


Paper:

TR05-080 | 21st July 2005 00:00

Proving NP-hardness for clique-width I: non-approximability of sequential clique-width


Abstract:

Clique-width is a graph parameter, defined by a composition mechanism
for vertex-labeled graphs, which measures in a certain sense the
complexity of a graph. Hard graph problems (e.g., problems
expressible in Monadic Second Order Logic, that includes NP-hard
problems) can be solved efficiently for graphs of certified small
clique-width. It is widely believed that determining the clique-width
of a graph is NP-hard; in spite of considerable efforts, no
NP-hardness proof has been found so far.

In this paper we show a non-approximability result for restricted form
of clique-width, termed r-sequential clique-width, considering only
such clique-width constructions where one of any two graphs put
together by disjoint union must have r or fewer vertices. In
particular, we show that for every positive integer r, the
r-sequential clique-width cannot be absolutely approximated in
polynomial time unless P=NP.

We show further that this non-approximability result holds even for
graphs of a very particular structure: for graphs obtained from
cobipartite graphs by replacing edges with induced paths. In part II
of this series of papers we use this strengthened result to show that,
unless P=NP, there is no polynomial-time absolute approximation
algorithm for (unrestricted) clique-width; this solves a problem that
has been open since the introduction of clique-width in the early
1990s.



ISSN 1433-8092 | Imprint