Given two graphs

G

and

G'

, the maximum common edge subgraph problem is the problem of finding a graph

H

with as many edges as possible which is

isomorphic In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...

to both a subgraph of

G

and a subgraph of

G'

. The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of

subgraph isomorphism In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs ''G'' and ''H'' are given as input, and one must determine whether ''G'' contains a subgraph that is isomorphic to ''H''. Subgraph isomorp ...

: a graph

H

is isomorphic to a subgraph of another graph

G

if and only if the maximum common edge subgraph of

G

and

H

has the same number of edges as

H

. Unless the two inputs

G

and

G'

to the maximum common edge subgraph problem are required to have the same number of vertices, the problem is

APX-hard In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor ap ...

References

Computational problems in graph theory {{algorithm-stub

See also

References