Given two graphs G {\displaystyle G} and G ′ {\displaystyle G'} , the maximum common edge subgraph problem (or MCES problem) is the problem of finding a graph H {\displaystyle H} with as many edges as possible which is isomorphic to both a subgraph of G {\displaystyle G} and a subgraph of G ′ {\displaystyle G'} . The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: a graph H {\displaystyle H} is isomorphic to a subgraph of another graph G {\displaystyle G} if and only if the maximum common edge subgraph of G {\displaystyle G} and H {\displaystyle H} has the same number of edges as H {\displaystyle H} . The problem also generalizes several other well-known graph problems, including maximum clique and maximum path. The problem is APX-hard, unless the two input graphs G {\displaystyle G} and G ′ {\displaystyle G'} are required to have the same number of vertices. The maximum common edge subgraph problem was first introduced by Bokhari in 1981 in the context of parallel programming applications in distributed memory environments. The problem also provides a measure of similarity between molecular structures. In computational biology, the problem is used for network alignment, which identifies mappings between biological networks to unravel common patterns. Applications include knowledge transfer between species, protein structure comparison, and studying human diseases. Non-biological applications include user privacy analysis in online social networks and object recognition in image analysis. A stricter variant of the MCES problem requires the common subgraph to be connected. This maximum common connected edge subgraph problem (or MCCES) is the formulation most commonly used in applications such as pattern recognition and chemistry, where finding disconnected fragments is typically not meaningful. The connectivity requirement does not change the computational complexity for general graphs, as the problem remains NP-complete, but it affects the structure of polynomial-time algorithms for restricted graph classes.
Algorithms Various algorithmic approaches have been developed for the maximum common edge subgraph problem. One strategy converts the problem to the maximum common clique problem, allowing the use of established clique-finding algorithms. Constraint programming approaches have also been explored, along with heuristic procedures designed for specific graph architectures that arise in practical applications. Integer programming formulations have received particular attention, beginning with the work of Marenco and Loiseau in 2003, which uses binary variables to represent vertex associations and edge selections while ensuring a proper bijection between graph vertices. In 2012, Bahiense, Manić, Piva, and de Souza proposed the BMPS formulation, which introduces variables representing direct edge-to-edge associations. This formulation is more expressive and has the advantage of a full-dimensional feasible region. An alternative approach by Almohamad and Duffuaa uses residual variables to count edges not present in the common subgraph. More recent work has explored the trade-offs between relaxation quality and computational efficiency. The symmetric formulation improves the linear programming relaxation by distinguishing the direction of edge mappings, though this comes at the cost of additional variables. Reduced formulations achieve a middle ground by aggregating variables to decrease problem size while attempting to maintain solution quality through techniques such as counting edges incident to mapped vertices. The polyhedral approach underlying these integer programming methods involves identifying valid inequalities and facet-defining constraints for the associated polytope. These constraints can be incorporated into branch and cut algorithms to improve solution times. Computational studies have revealed that the relative performance of different formulations depends on the structure of the input graphs, with smaller formulations typically exploring more nodes per second during search but potentially suffering from weaker linear relaxations. Simulated annealing approaches have been developed for large-scale instances of the problem, particularly for biological network alignment. These methods typically combine local search with perturbation strategies to escape local optima. One such algorithm uses iterated local search with a pheromone-based perturbation strategy adapted from ant colony optimization, and has been applied successfully to protein-protein interaction networks with thousands of vertices. While the MCCES problem is NP-hard for general graphs, polynomial-time algorithms have been developed for restricted graph classes:
… excerpt ends here. Continue reading the full article.
