Clique-width minimization is NP-hard

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

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.

Citation

Fellows, M. R., Rosamond, F. A., Rotics, U., & Szeider, S. (2006, May). Clique-width minimization is NP-hard. Presented at 38th Annual ACM Symposium on Theory of Computing, Seattle, Washington, USA

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 38th Annual ACM Symposium on Theory of Computing
• Start Date: May 21, 2006
• End Date: May 23, 2006
• Publication Date: May 1, 2006
• Deposit Date: Jan 23, 2009
• Publisher: Association for Computing Machinery (ACM)
• Pages: 354-362
• Series Title: Symposium on the Theory of Computing
• DOI: https://doi.org/10.1145/1132516.1132568
• Public URL: https://durham-repository.worktribe.com/output/1698028
• Publisher URL: http://doi.acm.org/10.1145/1132516.1132568
• Additional Information: Conference dates: 21-23 May 2006.