Maximum common edge subgraph

{{one source |date=April 2024}}

Given two graphs $G$ and $G\text{'}$, 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\text{'}$.

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\text{'}$ are required to have the same number of vertices.{{citation

| last1 = Bahiense | first1 = L.

| last2 = Manic | first2 = G.

| last3 = Piva | first3 = B.

| last4 = de Souza | first4 = C. C.

| doi = 10.1016/j.dam.2012.01.026

| issue = 18

| journal = Discrete Applied Mathematics

| pages = 2523–2541

| title = The maximum common edge subgraph problem: A polyhedral investigation

| volume = 160

| year = 2012| doi-access = free

}}.