Maximum common edge subgraph

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:

• For trees, the problem can be solved in polynomial time using maximum weight matching in bipartite graphs.

• For outerplanar graphs of bounded degree, a polynomial-time dynamic programming algorithm exists with time complexity O(n^{4D+4}), where D is the maximum vertex degree and n is the number of vertices. The algorithm uses the concept of "blades" and configurations to handle decompositions of biconnected components.

• For almost trees of bounded degree (graphs where each biconnected component has at most a constant number of edges beyond a spanning tree), polynomial-time algorithms are known.

The problem remains NP-hard for outerplanar graphs of unbounded degree and for partial k-trees of bounded degree when k \geq 11.

It is notable that outerplanar graph structures are particularly relevant for chemistry applications, as approximately 94% of chemical compounds in the NCI database have outerplanar graph structures.

Related problems

The maximum common edge subgraph problem should be distinguished from the maximum common subgraph isomorphism problem, which maximizes the number of vertices (in induced subgraphs) rather than edges. The vertex-maximizing version requires that both edges and non-edges be preserved in the mapping.

The multiple maximum common edge subgraph problem (or multi-MCES) generalizes the problem to more than two graphs. Given a set of graphs, the goal is to find a graph that is isomorphic to a subgraph of each input graph with the maximum number of edges. This variant is particularly relevant for comparing multiple biological networks simultaneously, such as finding conserved structures across multiple species.

References