<p>If I'm not mistaken your question was answered by <a href="http://dl.acm.org/citation.cfm?id=1427956">Chen-Thurley-Weyer-2008</a> modulo parameterized complexity assumptions. </p>

<p>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[1]$ complete (Corollary 4, page 6). </p>

<p>Thus it seems that unless the first level $W[1]$ of the $W$ hierarchy collapses to $FPT$, there is no such an infinite class of graphs whose induced subgraph isomorphism is in $P$. </p>

<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.</p>

CC BY-SA 3.0
2013-03-25T20:13:02.143Z
2013-03-25T20:59:09.963Z
2013-03-25T20:59:09.963Z
Mateus de Oliveira Oliveira
<p>Is there a sequence of undirected graphs $\{C_n\}_{n\in \mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem </p>

<blockquote>
  <p>Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$?</p>
</blockquote>

<p>is known to be in class $\mathsf{P}$? (For example, when $C_n=K_n$, this is the NP-complete clique problem.)</p>

CC BY-SA 3.0
2013-03-24T12:40:56.853Z
Crosspost from http://cs.stackexchange.com/questions/10576/
sdcvvc
CC BY-SA 3.0
2013-03-24T21:22:15.093Z
So $\{ C_n \}$ is part of the problem definition, $n$ is part of the input, and $G$ is part of the input?
Andrew D. King
CC BY-SA 3.0
2013-03-24T22:06:17.157Z
@Andrew D. King: Yes.
sdcvvc
CC BY-SA 3.0
2013-03-25T13:42:14.417Z
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.
Suresh Venkat
CC BY-SA 3.0
2013-03-25T13:59:29.387Z
@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.
sdcvvc
CC BY-SA 3.0
2013-03-25T18:34:04.900Z
think the answer is likely yes but the ${C_n}$ might be "contrived". consider the "near" [Induced subgraph isomorphism problem](http://en.wikipedia.org/wiki/Induced_subgraph_isomorphism_problem), NP-complete. basically every NP complete problem seems to have P subproblems for increasing size inputs. example: SAT and 2-SAT. to contrive the answer it might require mapping the problem onto SAT or some other "more standard" NP complete problem.
vzn
<cc.complexity-theory><graph-theory>
Is induced subgraph isomorphism easy on an infinite subclass?
sdcvvc
# Is induced subgraph isomorphism easy on an infinite subclass?

(Asked by: username_0 on 2013-03-24)

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.)

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_0**: Crosspost from http://cs.stackexchange.com/questions/10576/  
> **username_1**: So $\{ C_n \}$ is part of the problem definition, $n$ is part of the input, and $G$ is part of the input?  
> **username_0**: @username_1: Yes.  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_3**: think the answer is likely yes but the ${C_n}$ might be "contrived". consider the "near" [Induced subgraph isomorphism problem](http://en.wikipedia.org/wiki/Induced_subgraph_isomorphism_problem), NP-complete. basically every NP complete problem seems to have P subproblems for increasing size inputs. example: SAT and 2-SAT. to contrive the answer it might require mapping the problem onto SAT or some other "more standard" NP complete problem.  

---

## 1 answers

### Answer by username_4 on 2013-03-25. Score: 15 | Accepted answer

If I'm not mistaken your question was answered by [Chen-Thurley-Weyer-2008](http://dl.acm.org/citation.cfm?id=1427956) modulo parameterized complexity assumptions.

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[1]$ complete (Corollary 4, page 6).

Thus it seems that unless the first level $W[1]$ 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.


---

