Revision #1 Authors: Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Accepted on: 24th August 2005 00:00

Downloads: 2151

Keywords:

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.

TR05-080 Authors: Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Publication: 27th July 2005 16:27

Downloads: 1772

Keywords:

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.