Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Clique-width minimization is NP-hard.

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.

Abstract

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: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library