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 as many edges as possible which is isomorphic to both 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: 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'$ are required to have the same number of vertices.^[1]

References

^ Bahiense, L.; Manic, G.; Piva, B.; de Souza, C. C. (2012), "The maximum common edge subgraph problem: A polyhedral investigation", Discrete Applied Mathematics, 160 (18): 2523–2541, doi:10.1016/j.dam.2012.01.026.

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

[1] Bahiense, L.; Manic, G.; Piva, B.; de Souza, C. C. (2012), "The maximum common edge subgraph problem: A polyhedral investigation", Discrete Applied Mathematics, 160 (18): 2523–2541, doi:10.1016/j.dam.2012.01.026.

[1]

See also

References