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

Accepted on: 24th August 2005 00:00

Downloads: 986

Keywords:

Clique-width is a graph parameter that measures in a certain sense the

complexity of a graph. Hard graph problems (e.g., problems

expressible in Monadic Second Order Logic with second-order

quantification on vertex sets, 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. We give the first hardness proof. We show that

the clique-width of a given graph cannot be absolutely approximated in

polynomial time unless P=NP. We also show that, given a graph G and

an integer k, deciding whether the clique-width of 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-081 Authors: Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Publication: 27th July 2005 16:32

Downloads: 849

Keywords:

Clique-width is a graph parameter that measures in a certain sense the

complexity of a graph. Hard graph problems (e.g., problems

expressible in Monadic Second Order Logic with second-order

quantification on vertex sets, 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. We give the first hardness proof. We show that

the clique-width of a graph cannot be absolutely approximated in

polynomial time unless P=NP, this solves a problem that has been open

since the introduction of clique-width in the early 1990s.