Maximum Common Edge Subgraph (MCES)
A Maximum Common Edge Subgraph (MCES) is a Maximum Common Subgraph that has as may edges as possible.
- Context:
- It can be mapped by using a Maximum Common Edge Subgraph (MCES) Algorithm.
- It ranges from being a Connected Maximum Common Edge Subgraph to being a Disconnected Maximum Common Edge Subgraph.
- Example(s):
- Counter-Example(s):
- See: Maximum Common Edge Subgraph Task, Graph Theory, Graph Isomorphism, NP-Complete, Subgraph Isomorphism.
References
2018a
- (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Maximum_common_subgraph Retrieved:2018-11-20.
- In graph theory and theoretical computer science, a maximum common subgraph may mean either:
- Maximum common induced subgraph, a graph that is an induced subgraph of two given graphs and has as many vertices as possible.
- Maximum common edge subgraph, a graph that is a subgraph of two given graphs and has as many edges as possible.
- In graph theory and theoretical computer science, a maximum common subgraph may mean either:
2018b
- (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Maximum_common_edge_subgraph Retrieved:2018-11-25.
- 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].
- 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] .
- ↑ 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.
2018c
- (Duesbury et al., 2018) ⇒ Edmund Duesbury, John Holliday, and Peter Willett. (2018). “Comparison of Maximum Common Subgraph Isomorphism Algorithms for the Alignment of 2D Chemical Structures.” In: ChemMedChem Journal, 13(6). doi:10.1002/cmdc.201700482, PMID: 29057611
- QUOTE: There are two distinct types of MCS. The connected MCS (hereafter cMCS) represents the largest single fragment (in terms of either the number of atoms or the number of bonds) common to two compounds when they are aligned; whereas the disconnected MCS (hereafter dMCS) can contain multiple fragments and is the set of fragments that maximises the number of atoms or bonds in the MCS. The connected and disconnected forms of the MCS are illustrated in Figure 1. There are two additional subdivisions of the MCS: the maximum common edge‐induced subgraph (MCES) representing all the edges (i.e., bonds) between two graphs; and the maximum common node‐induced subgraph (MCIS) representing the nodes (i.e., atoms) in common between two graphs with their respective end‐points preserved.
Figure 1. Types of MCES (the MCS in each pair of compounds represented by bold edges): a) cMCS between the two molecular graphs; b) dMCS between the same two molecular graphs.
- QUOTE: There are two distinct types of MCS. The connected MCS (hereafter cMCS) represents the largest single fragment (in terms of either the number of atoms or the number of bonds) common to two compounds when they are aligned; whereas the disconnected MCS (hereafter dMCS) can contain multiple fragments and is the set of fragments that maximises the number of atoms or bonds in the MCS. The connected and disconnected forms of the MCS are illustrated in Figure 1. There are two additional subdivisions of the MCS: the maximum common edge‐induced subgraph (MCES) representing all the edges (i.e., bonds) between two graphs; and the maximum common node‐induced subgraph (MCIS) representing the nodes (i.e., atoms) in common between two graphs with their respective end‐points preserved.
2002
- (Raymond & Willett, 2002) ⇒ John W. Raymond, and Peter Willett. (2002). “Maximum Common Subgraph Isomorphism Algorithms for the Matching of Chemical Structures.” In: Journal of Computer-Aided Molecular Design, 16. doi:https://doi.org/10.1023/A:1021271615909
- QUOTE: Two graphs are said to be isomorphic if there is a one-to-one correspondence between their vertices and an edge only exists between two vertices in one graph if an edge exists between the two corresponding vertices in the other graph. An induced subgraph is a set [math]\displaystyle{ S }[/math] of vertices of a graph [math]\displaystyle{ G }[/math] and those edges of [math]\displaystyle{ G }[/math] with both end-points in [math]\displaystyle{ S }[/math]. A graph [math]\displaystyle{ G_{12} }[/math] is a common induced subgraph of graphs [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math] if [math]\displaystyle{ G_{12} }[/math] is isomorphic to induced subgraphs of [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math]. A maximum common induced subgraph (MCIS) consists of a graph [math]\displaystyle{ G_{12} }[/math] with the largest number of vertices meeting the aforementioned property. Related to the MCIS is the maximum common edge subgraph (MCES). An MCES is a subgraph consisting of the largest number of edges common to both [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math]. In this treatment, the term MCS will be used to denote both the MCIS and MCES problems.
Figure 1(a) illustrates an MCIS between two graphs (highlighted in bold), and Figure 1(b) demonstrates an MCES between the same two graphs. It is clear from Figure 1(b) that the MCES between the two graphs is simply the common subgraph with the largest number of edges. The MCIS in Figure 1(a) is less intuitive. The MCIS consists of the common subgraph with the largest number of vertices under the constraint that every edge present in graph [math]\displaystyle{ G_1(G_2) }[/math] that is incident on a vertex contained in the MCIS must also have a corresponding edge in the other graph [math]\displaystyle{ G_2(G_1) }[/math]. For instance, in the MCES, vertex 4 in graph [math]\displaystyle{ G_1 }[/math] maps to vertex 3' in graph [math]\displaystyle{ G_2 }[/math] because edges (3,4), (4,5), and (4,7) in [math]\displaystyle{ G_1 }[/math] correspond to edges (2' ,3' ), (3' ,4'), and (3',7' ) in [math]\displaystyle{ G_2 }[/math], respectively. In the MCIS, however, vertex 4 in [math]\displaystyle{ G_1 }[/math] does not match to vertex 3' in [math]\displaystyle{ G_2 }[/math], because there is an edge, (2,4), incident on vertex 4 in [math]\displaystyle{ G_1 }[/math] that does not have a corresponding edge incident on vertex 3' in [math]\displaystyle{ G_2. }[/math]
- QUOTE: Two graphs are said to be isomorphic if there is a one-to-one correspondence between their vertices and an edge only exists between two vertices in one graph if an edge exists between the two corresponding vertices in the other graph. An induced subgraph is a set [math]\displaystyle{ S }[/math] of vertices of a graph [math]\displaystyle{ G }[/math] and those edges of [math]\displaystyle{ G }[/math] with both end-points in [math]\displaystyle{ S }[/math]. A graph [math]\displaystyle{ G_{12} }[/math] is a common induced subgraph of graphs [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math] if [math]\displaystyle{ G_{12} }[/math] is isomorphic to induced subgraphs of [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math]. A maximum common induced subgraph (MCIS) consists of a graph [math]\displaystyle{ G_{12} }[/math] with the largest number of vertices meeting the aforementioned property. Related to the MCIS is the maximum common edge subgraph (MCES). An MCES is a subgraph consisting of the largest number of edges common to both [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math]. In this treatment, the term MCS will be used to denote both the MCIS and MCES problems.
