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$
8
  • $\begingroup$ Where does this question come from, what are your thoughts? $\endgroup$
    – Raphael
    Mar 18, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 13:00

1 Answer 1

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 and acknowledge you have read our privacy policy.

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