# Maximum common edge subgraph

Given two graphs ${\displaystyle G}$ and ${\displaystyle G'}$, the maximum common edge subgraph problem is the problem of finding a graph ${\displaystyle H}$ with as many edges as possible which is isomorphic to both a subgraph of ${\displaystyle G}$ and a subgraph of ${\displaystyle G'}$.
The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: a graph ${\displaystyle H}$ is isomorphic to a subgraph of another graph ${\displaystyle G}$ if and only if the maximum common edge subgraph of ${\displaystyle G}$ and ${\displaystyle H}$ has the same number of edges as ${\displaystyle H}$. Unless the two inputs ${\displaystyle G}$ and ${\displaystyle G'}$ to the maximum common edge subgraph problem are required to have the same number of vertices, the problem is APX-hard.[1]