Name
Abstract | ||
|---|---|---|
For every \epsilon 0, and integer q = 3, we show that given an N-vertex graph that has an induced q-colorable sub graph of size (1-\epsilon)N, it is NP-hard to find an independent set of size N/q^2. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/FOCS.2010.84 | Foundations of Computer Science |
Keywords | Field | DocType |
approximation theory,graph colouring,optimisation,set theory,NP-hardness,V-vertex graph,colorable graph,independent sets finding,PCPs,graph coloring,hardness of approximation | Integer,Discrete mathematics,Set theory,Combinatorics,Vertex (geometry),Polynomial,Hardness of approximation,Independent set,Mathematics,Path graph,Graph coloring | Conference |
ISSN | ISBN | Citations |
0272-5428 | 978-1-4244-8525-3 | 6 |
PageRank | References | Authors |
0.45 | 18 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Dinur | 1 | 1187 | 85.67 |
| Subhash Khot | 2 | 2064 | 112.51 |
| Will Perkins | 3 | 6 | 0.45 |
| Muli Safra | 4 | 149 | 12.53 |