Maximum common edge subgraph

Given two graphs $G$ and $G'$, the maximum common edge subgraph problem is the problem of finding a graph $H$ with a maximal number of edges which is isomorphic to 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. Unless $G$ and $G'$ are required to have the same number of vertices, the problem is APX-hard.

See also

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