2
$\begingroup$

Subgraph isomorphism

We have the graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$.

Question: Is the graph G_1 isomorphic with a subgraph of $G_2$ ?

(i.e. is there a subset of vertices of $G_2, V \subseteq V_2$ and subset of the edges of $G_2 E \subseteq E_2$ such that $|V|=|V_1|$ and $|E|=|E_1|$ and is there a one-to-one matching of the vertices of $G_1$ at the subset of vertices $V$ of $G_2 f:V_1 \to V$ such that $\{u,v\} \in E_1 \Leftrightarrow \{ f(u),f(v) \} \in E$)

In order to show that the problem is in NP, could we say the following?

A non-deterministic Turing machine can first "guess" which subgraph $G$ of $G_2$ is isomorphic with $G_1$ and then verify that $G$ is isomorphic with $G$ in $O(V_1+E_1)$ steps, since if we assume that the graphs are represented as adjacency lists, $G_1$ will have $O(V_1+E_1)$ elements.

Or could I improve something?

I want to show that the problem is NP-complete, reducing the clique problem to it (Hint: assume that the graph $G_1$ is complete)

Could you give me a hint how we could reduce the clique problem to our problem in order to show that the latter is NP-complete?

$\endgroup$
8
  • 1
    $\begingroup$ Your verification algorithm doesn't work (at least not as specified). Graph Isomorphism is not known to have a linear time algorithm. $\endgroup$
    – Yuval Filmus
    Apr 13, 2015 at 0:36
  • $\begingroup$ @YuvalFilmus How else could the verification step look like? $\endgroup$
    – Mary Star
    Apr 13, 2015 at 9:07
  • 1
    $\begingroup$ @evinda You need a stronger certificate (or: "guess" more). $\endgroup$
    – Tom van der Zanden
    Apr 13, 2015 at 10:13
  • $\begingroup$ What more could we guess for example? @TomvanderZanden $\endgroup$
    – Mary Star
    Apr 13, 2015 at 10:28
  • 1
    $\begingroup$ @evinda Something that helps you determine whether the subgraph is indeed isomorphic. (Note: there is no known polynomial algorithm for graph isomorphism, as Yuval noted you can't just say you can check this in linear time.) $\endgroup$
    – Tom van der Zanden
    Apr 13, 2015 at 11:02

1 Answer 1

Reset to default
5
$\begingroup$

The hint tells you pretty much everything:

Consider an arbitrary graph $G_{2}$ on $n$ vertices. Also per the suggestion of the hint, let $G_1$ be the complete graph on $k$ vertices, for some $k \le n$.

Is $G_{1}$ is isomorphic to a subgraph of $G_{2}$?

  • If yes, what does that tell you about $G_{2}$?
  • How can you use that to solve the max-clique problem?
$\endgroup$
11
  • $\begingroup$ If $G_1$ is isomorhic to a subgraph of $G_1$, don't we deduce from the fact that $G_1$ is a complete graph on $k$ vertices, that $G_2$ contains a complete subgraph of $k$ vertices? $$$$ I found the following: "A maximum clique of a graph, G, is a clique, such that there is no clique with more vertices.". So in order to solve the max-clique problem, do we assume that all the $k$ vertices of the subgraph of $G_2$ are connected to each other but all the $n-k+1$ remaining vertices aren't connected to any other vertex? Or have I understood it wrong? $\endgroup$
    – Mary Star
    Apr 13, 2015 at 9:32
  • 1
    $\begingroup$ A clique of size $k$ is a complete graph on $k$ vertices. As you said, if $G_{1}$ is isomorphic to a subgraph of $G_{2}$, then we conclude that $G_{2}$ contains a clique of size $k$. How can you check if $G_{2}$ contains a clique of size $k+1$? $\endgroup$
    – megas
    Apr 13, 2015 at 15:53
  • $\begingroup$ If $G_2$ would contain a clique of size $k+1$, then $G_2$ couldn't contain a clique of size $k$ that is isomorphic with $G_1$ because the $k+1$-th element of the clique of size $k+1$ would be adjacent to all the other vertices of the graph and so the clique of size $k$ of the graph $G_2$ will have more edges than the graph $G_1$. Or am I wrong? $\endgroup$
    – Mary Star
    Apr 13, 2015 at 16:20
  • 1
    $\begingroup$ No, that is not correct. If $G_{2}$ contains a clique of size $k+1$, then it will also contain (many) subgraphs that are isomorphic to a complete graph on $k$ vertices. Take a step back; the answer is right in front of you! We have a black box to check if a graph $G_{2}$ contains a clique of size $k$. (What is $k$? -- Any number you want, right?). Lets say that $G_{2}$ contains a max clique of size $9$. We know that this is the max clique if $G_{2}$ does not contain a clique of size $10, \dots, n$. But we already have a black box to check that. Do you see it now? $\endgroup$
    – megas
    Apr 13, 2015 at 16:42
  • $\begingroup$ If $G_2$ contains a clique of size $k+1$ will it necessarily contain many subgraphs that are isomorhic to a complete graph on $k$ vertices? If so, could you explain me why? $$$$ Also, we have a black box to check if a graph contains a clique of size $k$. So in order to determine if $G_2$ contains a clique of size $k+1$, we will ask the black box, right? $$$$ $G_2$ contains a max clique of size $V_2$, right? $$$$ So, in order to solve the max-clique problem, do we have to assume that $G_1$ is a complete graph on $n$ vertices and check if $G_1$ is isomorphic to $G_2$ ? $\endgroup$
    – Mary Star
    Apr 13, 2015 at 17:43

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.