18

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

sdcvvc
  • 1,291
  • 9
  • 19
  • Crosspost from http://cs.stackexchange.com/questions/10576/ – sdcvvc Mar 24 '13 at 12:40
  • 1
    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 Mar 24 '13 at 21:22
  • 1
    @Andrew D. King: Yes. – sdcvvc Mar 24 '13 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. – Suresh Venkat Mar 25 '13 at 13:42
  • 4
    @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 Mar 25 '13 at 13:59
  • think the answer is likely yes but the ${C_n}$ might be "contrived". consider the "near" 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 Mar 25 '13 at 18:34

1 Answers1

15

If I'm not mistaken your question was answered by Chen-Thurley-Weyer-2008 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.

Mateus de Oliveira Oliveira
  • 3,052
  • 21
  • 27