Finding induced trees
Let G=(V(G),E(G)) G = ( V ( G ) , E ( G ) ) be a finite connected undirected graph and W?V(G) W ? V ( G ) a subset of vertices. We are searching for a subset X?V(G) X ? V ( G ) such that W?X W ? X and the subgraph induced on X X is a tree. NP N P -completeness results and polynomial time algorithms are given assuming that the cardinality of W W is fixed or not. Besides we give complexity results when X X has to induce a path or when G G is a weighted graph. We also consider problems where the cardinality of X X has to be minimized.
induced tree polynomial time algorithm induced subgraph np n p -completeness np n p np n p n p