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$
0

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ In other words, it is NP-hard. Well-known special cases are CLIQUE and HAMILTONIAN CYCLE. $\endgroup$ Nov 15, 2016 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, 2016 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$ Nov 16, 2016 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, 2016 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.