Parameterized complexity of finding connected induced subgraphs

For a graph property Π, i.e., a family Π of graphs, the Connected InducedΠ-Subgraph problem asks whether an input graph G contains k   vertices V′V′ such that the induced subgraph G[V′]G[V′] is connected and satisfies property Π.In this paper, we study the parameterized complexity of Connected InducedΠ-Subgraph for decidable hereditary properties Π, and give a nearly complete characterization in terms of whether Π includes all complete graphs, all stars, and all paths. As a consequence, we obtain a complete characterization of the parameterized complexity of our problem when Π is the family of H-free graphs for a fixed graph H   with h≥3h≥3 vertices: W[1]-hard if H   is KhKh, Kh‾, or K1,h−1K1,h−1; and FPT otherwise. Furthermore, we also settle the parameterized complexity of the problem for many well-known families Π of graphs: FPT for perfect graphs, chordal graphs, and interval graphs, but W[1]-hard for forests, bipartite graphs, planar graphs, line graphs, and degree-bounded graphs.