0
$\begingroup$

I am confused about the definition of sub graph isomorphism, wikipedia says that the subgraph isomorphism problem is a computational task in which two graphs $G$ and $H$ are given as input, and one must determine whether $G$ contains a subgraph that is isomorphic to $H$.

Is this the correct statement or is it whether $G$ contains a subgraph that is isomorphic to a subgraph in $H$?

$\endgroup$
1
$\begingroup$

No, that is not the correct statement.

Every graph contains the empty graph as a subgraph, the problem as you define it would return TRUE for all pairs of graphs, which isn't very interesting.

Finding the largest common subgraph of two graphs would be an interesting problem, and it is at least as hard as the actual subgraph isomorphism problem (since $G$ contains a subgraph isomorphic to $H$ if and only if the largest common subgraph is isomorphic to $H$.)

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