Maximum common edge subgraph

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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