| Popis: |
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 ' such that the induced subgraph 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 ? 3 vertices: W1-hard if H is K h , K h ? , or K 1 , 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 W1-hard for forests, bipartite graphs, planar graphs, line graphs, and degree-bounded graphs. |
Full Text from ScienceDirect