کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435718 | 689930 | 2015 | 11 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 607, Part 1, 23 November 2015, Pages 49–59