- Title
- Clique width minimization is NP-hard
- Creator
- Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan
- Relation
- STOC '06 . Proceedings of the 38th Annual ACM Symposium on Theory of Computing (Seattle, WA, USA May 21-23) p. 354-362
- Publisher Link
- http://dx.doi.org/10.1145/1132516.1132568
- Publisher
- ACM Press
- Resource Type
- conference paper
- Date
- 2006
- Description
- 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.
- Subject
- NP-completeness; absolute approximation; clique-width; pathwidth
- Identifier
- http://hdl.handle.net/1959.13/31715
- Identifier
- uon:2778
- Identifier
- ISBN:1595931341
- Language
- eng
- Reviewed
- Hits: 1702
- Visitors: 1871
- Downloads: 1
Thumbnail | File | Description | Size | Format |
---|