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
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
and a subgraph of
.
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
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
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 ...
.
[.]
See also
*
Maximum common subgraph isomorphism problem
*
Subgraph isomorphism problem 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 ...
*
Induced subgraph isomorphism problem
In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph.
Problem statement
Formally, the problem takes as input two graphs ...
References
Computational problems in graph theory
{{algorithm-stub