2
$\begingroup$

Given $n_1$ and $n_2$ number of verteces and the adjacency matrix for both graphs, one should determine whether $G_2$ is a subgraph of $G_1$.

I am supposed to use C++ for this, and though I could probably come out with a solution including $20$ for functions, it's most likely not the best approach to the exercise.

Do I have to(?):

  • Assume the graphs have $n_2$ common vertices (because this has to be in order for $G_2$ to be a subgraph of $G_1$, right?)
  • Check to see if any of the $\begin{pmatrix}n_1\\ n_1-n_2\end{pmatrix}$ possibly resulting graphs after the removal of $n_1-n_2$ vertices from $G_1$ is equal to $G_2$

Althogh not sure how to compute the above.

This must be an easy exercise since it's for beginners in graphs, but I guess there's just something I am missing. Could you give me some hints on how to approach this in a better way? I've looked for this one a while, hopefully it's not a duplicate.

$\endgroup$
0
$\begingroup$

This problem is more general form of the graph isomorphism problem. No polynomial time algorithm is known solving it. The state of the art suggests possible approaches.

| cite | improve this answer | |
$\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.