Given two graphs
G
and
G
′
, the maximum common edge subgraph problem is the problem of finding a graph
H
with as many edges as possible which is isomorphic to both a subgraph of
G
and a subgraph of
G
′
.
The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: a graph
H
is isomorphic to a subgraph of another graph
G
if and only if the maximum common edge subgraph of
G
and
H
has the same number of edges as
H
. Unless the two inputs
G
and
G
′
to the maximum common edge subgraph problem are required to have the same number of vertices, the problem is APX-hard.
