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.
