C. Lund, and M. Yannakakis. Automata, Languages and Programming, page 40--51. Berlin, Heidelberg, Springer Berlin Heidelberg, (1993)
We consider the following class of problems: given a graph, find the maximum number of nodes inducing a subgraph that satisfies a desired property $\pi$, such as planar, acyclic, bipartite, etc. We show that this problem is hard to approximate for any property $\pi$ on directed or undirected graphs that is nontrivial and hereditary on induced subgraphs.