Clique-Width is NP-Complete

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

SIAM Journal on Discrete Mathematics (SIDMA) vol. 23, no. 2, pp. 909-939, 2009.

A preliminary and shortened version of this paper appeared in the proceedings of STOC 2006; 38th ACM Symposium on Theory of Computing, Seattle, Washington, USA, pp. 354—362, ACM Press, 2006.

This paper combines the results of the technical reports:
  • Proving NP-hardness for clique-width I: non-approximability of sequential clique-width; Electronic Colloquium on Computational Complexity (ECCC)
    Report TR05-080, Revision 01
    (ISSN 1433-8092, 12th Year, 80th Report)
  • Proving NP-hardness for clique-width II: non-approximability of clique-width; Electronic Colloquium on Computational Complexity (ECCC)
    Report TR05-081, Revision 01
    (ISSN 1433-8092, 12th Year, 81th Report)

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 certified small clique-width. 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.

Download:  [paper pdf]