Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes

We investigate the parameterized complexity of finding subgraphs with hereditary properties on graphs belonging to a hereditary graph class. Given a graph G, a non-trivial hereditary property \(\varPi \) and an integer parameter k, the general problem \(P(G,\varPi ,k)\) asks whether there exists k vertices of G that induce a subgraph satisfying property \(\varPi \). This problem, \(P(G,\varPi ,k)\) has been proved to be \(\mathsf {NP}\)-complete by Lewis and Yannakakis. The parameterized complexity of this problem is shown to be \(\mathsf {W}[1]\)-complete by Khot and Raman, if \(\varPi \) includes all trivial graphs (graphs with no edges) but not all complete graphs and vice versa; and is fixed-parameter tractable, otherwise. As the problem is \(\mathsf {W}[1]\)-complete on general graphs when \(\varPi \) includes all trivial graphs but not all complete graphs and vice versa, it is natural to further investigate the problem on restricted graph classes.