I'm studying for my computation exam and came across the following question:
Given a Graph $G=(V_G,E_G)$,
$G$ contains a copy of $H=(V_H,E_H)$ if there exists a subgroup of $S\subseteq$$V_G$ of size |$V_H$|
s.t the subgraph induced by $S$ is isomorphic to $H$.
Assuming $P\neq NP$, is the following language is in $P$ or is it $NPC$?
$L_G=\{H| G$ contains a copy of $H\}$ for some fixed graph $G$
I'm kind of stuck with how to approach it, I know a fixed graph $G$ means I only need to verify a fixed set of subgraphs but is there anything else this gives me?
Thanks!
To decide the language $L_G$, we take only $H$ as an input, and then determine if there is a copy of $H$ inside $G$. So we only need to find an algorithm that's polynomial in the size of $H$.
To do this, begin by rejecting $H$ if $H$ has more vertices than $G$; this step is polynomial, and for all sufficiently large inputs it is all we have to do. If $H$ does not have more vertices than $G$, then a brute-force algorithm suffices to finish: check all injective functions $V_H \to V_G$ to see if any of them are isomorphisms between $H$ and a subgraph of $G$. (There could be as many as $|V(G)|!$ such functions, but we don't care; that's still a constant.)
Note that this is very different from deciding the language $$L = \{(G,H) \mid G \text{ contains a copy of } H\}$$ where both $G$ and $H$ are taken as inputs. This language is NP-complete for many reasons, such as the fact that it has the Hamiltonian cycle problem as a special case.