[Solved]: Is induced subgraph isomorphism easy on an infinite subclass?

Problem Detail: 

Is there a sequence of undirected graphs $\{C_n\}_{n\in \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