Name
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, 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/070687256 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
second-order quantification,graph parameter,monadic second-order logic,vertex set,certain sense,polynomial time,hard graph problem,np-hard problem,problems expressible,bounded clique-width,np completeness,pathwidth,clique width | Discrete mathematics,Block graph,Circulant graph,Combinatorics,Line graph,Clique graph,Cubic graph,Null graph,Butterfly graph,Voltage graph,Mathematics | Journal |
Volume | Issue | ISSN |
23 | 2 | 0895-4801 |
Citations | PageRank | References |
55 | 1.43 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael R. Fellows | 1 | 4138 | 319.37 |
| Frances A. Rosamond | 2 | 304 | 15.94 |
| Udi Rotics | 3 | 715 | 33.68 |
| Stefan Szeider | 4 | 1341 | 99.97 |