6
$\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}$?

$\endgroup$
  • $\begingroup$ Where does this question come from, what are your thoughts? $\endgroup$ – Raphael Mar 18 '13 at 7:36
  • $\begingroup$ @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. $\endgroup$ – sdcvvc Mar 18 '13 at 9:46
  • $\begingroup$ 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. $\endgroup$ – user742 Mar 18 '13 at 10:17
  • $\begingroup$ @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) $\endgroup$ – sdcvvc Mar 18 '13 at 10:22
  • $\begingroup$ @sdcvvc, I read your question in reverse, I though you checking is G is subgraph of any C_n, my mistake. $\endgroup$ – user742 Mar 18 '13 at 13:00
2
$\begingroup$

This question has been answered on cstheory.

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

$\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.