Hardness of Finding Independent Sets in Almost 3-Colorable Graphs.

Irit Dinur Subhash Khot Will Perkins Muli Safra

Published in: FOCS (2010)

Keyphrases

computational complexity
database
directed graph
search engine
np hard
graph databases
graph representation
graph theoretic