# Maximum/minimum intersection of two graphs

I wonder if the following graph problems have been studied and have names.

Problem(s). Given two $n$-vertex unlabeled graphs $G_1$ and $G_2$, find their maximum/minimum edge intersection. That is find two labeled graphs $H_1 = ([n], E_1)$ and $H_2 = ([n],E_2)$ such that $H_1 \simeq G_1$, $H_2 \simeq G_2$, and $|E_1 \cap E_2|$ is maximized/minimized.

It would also be helpful to know if these problems have been studied for special classes of graphs, e.g. for trees.

## 1 Answer

This is essentially the Maximum common edge subgraph problem, which is at least as hard as the subgraph isomorphism problem.

• In other words, it is NP-hard. Well-known special cases are CLIQUE and HAMILTONIAN CYCLE. – Brendan McKay Nov 15 '16 at 23:22
• @BrendanMcKay, thanks for the observation! I cannot see why the HAMILTONIAN CYCLE is a special case of the problem. I see how to reduce the HAMILTONIAN CYCLE to the problem, but does it really coincide with some special case of the problem? – Victor Nov 16 '16 at 8:25
• @Victor Let $G_1$ be a given graph on $n$ vertices and $G_2$ be the $n$ vertex cycle graph. Then $G_1$ has a Hamiltonian cycle if and only if the maximum edge intersection is $n$. – Michael Biro Nov 16 '16 at 13:01
• @MichaelBiro This shows how to solve the HAMILTONIAN CYCLE problem (HC), when you know how to solve the Maximum Common Edge Subgraph problem (MCES) (this what I meant by reduction from HC to MCES). But how can you solve MCES (with $G_1$ being a cycle) when you know how to solve HC? – Victor Nov 16 '16 at 14:50