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

Improve this question
$\endgroup$
6
  • $\begingroup$ Crosspost from cs.stackexchange.com/questions/10576 $\endgroup$
    – sdcvvc
    Mar 24, 2013 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, 2013 at 21:22
  • 1
    $\begingroup$ @Andrew D. King: Yes. $\endgroup$
    – sdcvvc
    Mar 24, 2013 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, 2013 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, 2013 at 13:59

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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