Maximum common edge subgraph

Template:One source Given two graphs $G$ and $G^{\prime }$, the maximum common edge subgraph problem is the problem of finding a graph $H$ with as many edges as possible which is isomorphic to both a subgraph of $G$ and a subgraph of $G^{\prime }$.

The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: 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$. The problem is APX-hard, unless the two input graphs $G$ and $G^{\prime }$ are required to have the same number of vertices.

See also

• Maximum common subgraph isomorphism problem
• Subgraph isomorphism problem
• Induced subgraph isomorphism problem

References

Template:Algorithm-stub Template:Graph-stub