# Reduce our problem to a known np-complete problem

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?

• Your verification algorithm doesn't work (at least not as specified). Graph Isomorphism is not known to have a linear time algorithm. – Yuval Filmus Apr 13 '15 at 0:36
• @YuvalFilmus How else could the verification step look like? – Mary Star Apr 13 '15 at 9:07
• @evinda You need a stronger certificate (or: "guess" more). – Tom van der Zanden Apr 13 '15 at 10:13
• What more could we guess for example? @TomvanderZanden – Mary Star Apr 13 '15 at 10:28
• @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.) – Tom van der Zanden Apr 13 '15 at 11:02

## 1 Answer

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?
• 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? – Mary Star Apr 13 '15 at 9:32
• 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$? – megas Apr 13 '15 at 15:53
• 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? – Mary Star Apr 13 '15 at 16:20
• 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? – megas Apr 13 '15 at 16:42
• 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$ ? – Mary Star Apr 13 '15 at 17:43