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

. 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.^[1]

See also