Summary: We consider the parameterized complexity of the following problem under the framework introduced by Downey and Fellows: Given a graph \(G\), an integer parameter \(k\) and a non-trivial hereditary property \(\Pi\), are there \(k\) vertices of \(G\) that induce a subgraph with property \(\Pi\)? This problem has been proved NP-hard by Lewis and Yannakakis. We show that if \(\Pi\) includes all independent sets but not all cliques or vice versa, then the problem is hard for the parameterized class \(W[1]\) and is fixed parameter tractable otherwise. In the former case, if the forbidden set of the property is finite, we show, in fact, that the problem is \(W[1]\)-complete. Our proofs, both of the tractability as well as the hardness ones, involve clever use of Ramsey numbers.
For the entire collection see [Zbl 0941.00031].