Loading...
Please wait, while we are loading the content...
Similar Documents
Proving np-hardness for clique-width ii: non-approximability of clique-width (2005).
| Content Provider | CiteSeerX |
|---|---|
| Author | Rosamond, Frances A. Rotics, Udi Szeider, Stefan |
| Description | This content is published in/by ELECTRONIC COLLOQUIUM ON COMPUTATIONAL COMPLEXITY, REPORT NO. 81 |
| 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 certified 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 graph cannot be absolutely approximated in polynomial time unless P = NP, this solves a problem that has been open since the introduction of clique-width in the early 1990s. |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Clique-width Ii Vertex Set Graph Cannot Certain Sense First Hardness Proof Graph Parameter Second-order Quantification Hard Graph Problem Monadic Second Order Logic Np-hard Problem Np-hardness Proof Polynomial Time Certified Small Clique-width Considerable Effort |
| Content Type | Text |
