Fellows, M. R. and Rosamond, F. A. and Rotics, U. and Szeider, S. (2006) 'Clique-width minimization is NP-hard.', 38th Annual ACM Symposium on Theory of Computing Seattle, Washington, USA, 21-23 May 2006.
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 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 NPhy complete. This solves a problem that has been open since the introduction of clique-width in the early 1990s.
|Item Type:||Conference item (Paper)|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://doi.acm.org/10.1145/1132516.1132568|
|Record Created:||23 Jan 2009|
|Last Modified:||27 Nov 2009 14:08|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|