18
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Crosspost from cs.stackexchange.com/questions/10576 $\endgroup$ – sdcvvc Mar 24 '13 at 12:40
  • 1
    $\begingroup$ So $\{ C_n \}$ is part of the problem definition, $n$ is part of the input, and $G$ is part of the input? $\endgroup$ – Andrew D. King Mar 24 '13 at 21:22
  • 1
    $\begingroup$ @Andrew D. King: Yes. $\endgroup$ – sdcvvc Mar 24 '13 at 22:06
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Mar 25 '13 at 13:42
  • 4
    $\begingroup$ @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. $\endgroup$ – sdcvvc Mar 25 '13 at 13:59
15
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.