1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ In other words, it is NP-hard. Well-known special cases are CLIQUE and HAMILTONIAN CYCLE. $\endgroup$ – Brendan McKay Nov 15 '16 at 23:22
  • $\begingroup$ @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? $\endgroup$ – Victor Nov 16 '16 at 8:25
  • $\begingroup$ @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$. $\endgroup$ – Michael Biro Nov 16 '16 at 13:01
  • $\begingroup$ @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? $\endgroup$ – Victor Nov 16 '16 at 14:50

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.