Maximum common edge subgraph explained

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

. The problem is APX-hard, unless the two input graphs

and

are required to have the same number of vertices.^[1]

See also