# 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}$?

• Where does this question come from, what are your thoughts?
– Raphael
Mar 18 '13 at 7:36
• @Raphael - The question popped into my head after seeing cs.stackexchange.com/questions/10573. I don't have intuition what the answer is - either there should be a nice family of graphs (perhaps an increasing chain) where finding the subgraph is easier because of the structure of the graphs, or a reduction from something NP-hard. For example, Ramsey's theorem states that for large $n$, there should be clique or independent set, but the dependency in $n$ is too weak to make a reduction. Mar 18 '13 at 9:46
• Set $C_n$ as complete graph of size $n$, then is easy to verify given graph is induced subgraph of one of a $C_n$ (in $P$). I don't know, may be I didn't get your question.
– user742
Mar 18 '13 at 10:17
• @Saeed: It's the other way round: the problem is asking if $C_n \leq G$, which is the NP-complete clique problem (note that $G$ does not have to have $n$ vertices) Mar 18 '13 at 10:22
• @sdcvvc, I read your question in reverse, I though you checking is G is subgraph of any C_n, my mistake.
– user742
Mar 18 '13 at 13:00

Digest: Chen,Thurley and Weyer (2008) prove that this problem is $W[1]$-hard for every infinite class of graphs.