# Is induced subgraph isomorphism easy on an infinite subclass?

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}$? (For example, when $C_n=K_n$, this is the NP-complete clique problem.)

• Crosspost from cs.stackexchange.com/questions/10576 Mar 24, 2013 at 12:40
• So $\{ C_n \}$ is part of the problem definition, $n$ is part of the input, and $G$ is part of the input? Mar 24, 2013 at 21:22
• @Andrew D. King: Yes. Mar 24, 2013 at 22:06
• What about if $C_n$ is a star (one central node connected to $n-1$ nodes that form an independent set)? to check, merely enumerate all nodes of degree $n-1$ in $G$, and check if the neighbors form an independent set. Mar 25, 2013 at 13:42
• @Suresh: There may be a vertex of degree larger than $n-1$, whose some $n-1$ neighbors form an independent set. Finding them is NP-complete. Mar 25, 2013 at 13:59

I didn't read the paper carefully yet, but as far as I understood, there is a dichotomy in the sense that if $C$ is finite then the problem is in $P$, but if $C$ has an infinite number of graphs then the induced subgraph isomorphism is $W$ complete (Corollary 4, page 6).
Thus it seems that unless the first level $W$ of the $W$ hierarchy collapses to $FPT$, there is no such an infinite class of graphs whose induced subgraph isomorphism is in $P$.
There is another interesting result stating that if $P\neq NP$ then there are classes for which the induced isomorphism is neither in $P$ nor $NP$ complete.