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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .