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}$?
$\begingroup$
$\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$– sdcvvcMar 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$– user742Mar 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$– sdcvvcMar 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$– user742Mar 18, 2013 at 13:00
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
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.