Misplaced Pages

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Maximum common edge subgraph" – news · newspapers · books · scholar · JSTOR (April 2024)

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}$. The problem is APX-hard, unless the two input graphs ${\displaystyle G}$ and ${\displaystyle G'}$ are required to have the same number of vertices.

See also

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

References

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.

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

• v
• t
• e

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

• v
• t
• e

• Computational problems in graph theory
• Algorithms and data structures stubs
• Graph theory stubs