Maximum common edge subgraph

Given two graphs $G$ and $G'$, the maximum common edge subgraph problem (or MCES problem) is the problem of finding a graph $H$ with as many edges as possible which is isomorphic to both a subgraph of $G$ and a subgraph of $G'$.

The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: a graph $H$ is isomorphic to a subgraph of another graph $G$ if and only if the maximum common edge subgraph of $G$ and $H$ has the same number of edges as $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$ and $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:

• 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.

See also

• Subgraph isomorphism problem
• Induced subgraph isomorphism problem