- Title
- Clique-width is NP-complete
- Creator
- Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan
- Relation
- Siam Journal on Discrete Mathematics Vol. 23, Issue 2, p. 909-939
- Publisher Link
- http://dx.doi.org/10.1137/070687256
- Publisher
- Society for Industrial and Applied Mathematics
- Resource Type
- journal article
- Date
- 2009
- 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, which includes NP-hard problems such as 3-colorability) can be solved in polynomial time for graphs of bounded 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.
- Subject
- clique-width; NP-completeness; pathwidth; absolute approximation
- Identifier
- uon:6974
- Identifier
- http://hdl.handle.net/1959.13/925230
- Identifier
- ISSN:0895-4801
- Reviewed
- Hits: 1326
- Visitors: 1504
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|