Given two graphs G {\displaystyle G} and G ′ {\displaystyle G'} , the maximum common edge subgraph problem is the problem of finding a graph H {\displaystyle H} with as many edges as possible which is isomorphic to both a subgraph of G {\displaystyle G} and a subgraph of G ′ {\displaystyle G'} .

The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: a graph H {\displaystyle H} is isomorphic to a subgraph of another graph G {\displaystyle G} if and only if the maximum common edge subgraph of G {\displaystyle G} and H {\displaystyle H} has the same number of edges as H {\displaystyle H} . The problem is APX-hard, unless the two input graphs G {\displaystyle G} and G ′ {\displaystyle G'} are required to have the same number of vertices.