Maximum common edge subgraph

Given two graphs

G

{\displaystyle G}

and

G

′

{\displaystyle G'}

, the maximum common edge subgraph problem (or MCES 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 also generalizes several other well-known graph problems, including maximum clique and maximum path. 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.

The maximum common edge subgraph problem was first introduced by Bokhari in 1981 in the context of parallel programming applications in distributed memory environments. The problem also provides a measure of similarity between molecular structures. In computational biology, the problem is used for network alignment, which identifies mappings between biological networks to unravel common patterns. Applications include knowledge transfer between species, protein structure comparison, and studying human diseases. Non-biological applications include user privacy analysis in online social networks and object recognition in image analysis.

A stricter variant of the MCES problem requires the common subgraph to be connected.