ECCC-Report TR05-081https://eccc.weizmann.ac.il/report/2005/081Comments and Revisions published for TR05-081en-usWed, 24 Aug 2005 00:00:00 +0300
Revision 1
| Proving NP-hardness for clique-width II: non-approximability of clique-width |
Michael R. Fellows,
Frances A. Rosamond,
Udi Rotics,
Stefan Szeider
https://eccc.weizmann.ac.il/report/2005/081#revision1Clique-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.
Wed, 24 Aug 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/081#revision1
Paper TR05-081
| Proving NP-hardness for clique-width II: non-approximability of clique-width |
Michael R. Fellows,
Frances A. Rosamond,
Udi Rotics,
Stefan Szeider
https://eccc.weizmann.ac.il/report/2005/081Clique-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.
Wed, 27 Jul 2005 16:32:40 +0300https://eccc.weizmann.ac.il/report/2005/081