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