Maximum common edge subgraph


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