Problem Detail: Is there a sequence of undirected graphs ${C_n}_{nin mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem
Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$?
is known to be in class $mathsf{P}$?
Asked By : sdcvvc
Answered By : frafl
This question has been answered on cstheory. Digest: Chen,Thurley and Weyer (2008) prove that this problem is $W[1]$-hard for every infinite class of graphs.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10576 Ask a Question Download Related Notes/Documents