patternMinor
Is induced subgraph isomorphism easy on an infinite subclass?
Viewed 0 times
infiniteinducedeasysubclasssubgraphisomorphism
Problem
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}$?
Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$?
is known to be in class $\mathsf{P}$?
Solution
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.
Digest: Chen,Thurley and Weyer (2008) prove that this problem is $W[1]$-hard for every infinite class of graphs.
Context
StackExchange Computer Science Q#10576, answer score: 2
Revisions (0)
No revisions yet.