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, 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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1132516.1132568 | STOC |
Keywords | Field | DocType |
graph parameter,monadic second order logic,np-hardness proof,clique-width minimization,graph g,hard graph problem,np-hard problem,problems expressible,integer k,hardness proof,small clique-width,polynomial time,clique width,np completeness,np hard problem,second order,pathwidth | Discrete mathematics,Circulant graph,Combinatorics,Line graph,Clique graph,Cubic graph,Null graph,Clique-width,Mathematics,Voltage graph,Complement graph | Conference |
ISBN | Citations | PageRank |
1-59593-134-1 | 32 | 1.20 |
References | Authors | |
28 | 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 |