Timeline for Maximum/minimum intersection of two graphs
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 16, 2016 at 14:50 | comment | added | Victor | @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? | |
| Nov 16, 2016 at 13:01 | comment | added | Michael Biro | @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$. | |
| Nov 16, 2016 at 8:25 | comment | added | Victor | @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? | |
| Nov 16, 2016 at 7:45 | vote | accept | Victor | ||
| Nov 15, 2016 at 23:22 | comment | added | Brendan McKay | In other words, it is NP-hard. Well-known special cases are CLIQUE and HAMILTONIAN CYCLE. | |
| Nov 15, 2016 at 20:44 | history | answered | Michael Biro | CC BY-SA 3.0 |