Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries Journal: PACMMOD Volume: 4 3 (SIGMOD) 128 6 DOI: 10.1145/3802005 CCS: Mathematics of computing Combinatorial optimization CCS: Mathematics of computing Graph algorithms CCS: Theory of computation Branch-and-bound CCS: Mathematics of computing Combinatorial algorithms

Buddhi Kothalawala, Henning Koehler, Muhammad Farhan · 2026

Read Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries Journal: PACMMOD Volume: 4 3 (SIGMOD) 128 6 DOI: 10.1145/3802005 CCS: Mathematics of computing Combinatorial optimization CCS: Mathematics of computing Graph algorithms CCS: Theory of computation Branch-and-bound CCS: Mathematics of computing Combinatorial algorithms by Buddhi Kothalawala, Henning Koehler, Muhammad Farhan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-23031.txt.

Introduction

Kothalawala, Koehler, and Farhan speed up maximum common subgraph computation by exploiting symmetry. The problem finds the largest shared part of two graphs. Symmetry can prune search, but past methods used only one graph's symmetries. Their framework breaks symmetries in both the variable and value graphs. Modular symmetries come from local neighborhood structure. Pruning cuts isomorphic subtrees while keeping optimality exact. Benchmark tests beat the prior top method, RRSplit. More cases are solved, with far less time and search.

Catalog record

CREATORBuddhi Kothalawala, Henning Koehler, Muhammad Farhan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74880
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.23031

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries Journal: PACMMOD Volume: 4 3 (SIGMOD) 128 6 DOI: 10.1145/3802005 CCS: Mathematics of computing Combinatorial optimization CCS: Mathematics of computing Graph algorithms CCS: Theory of computation Branch-and-bound CCS: Mathematics of computing Combinatorial algorithms Buddhi Kothalawala, Henning Koehler, Muhammad Farhan Abstract . The Maximum Common Subgraph (MCS) problem plays a key role in many applications, including cheminformatics, bioinformatics, and pattern recognition, where it is used to identify the largest shared substructure between two graphs. Although symmetry exploitation is a powerful means of reducing search space in combinatorial optimization, its potential in MCS algorithms has remained largely underexplored due to the challenges of detecting and integrating symmetries effectively. Existing approaches, such as RRSplit, partially address symmetry through vertex-equivalence reasoning on the variable graph, but symmetries in the value graph remain unexploited. In this work, we introduce a complete dual-symmetry breaking framework that simultaneously handles symmetries in both variable and value graphs. Our method identifies and exploits modular symmetries based on local neighborhood structures, allowing the algorithm to prune isomorphic subtrees during search while rigorously preserving optimality. Extensive experiments on standard MCS benchmarks show that our approach substantially outperforms the state-of-the-art RRSplit algorithm, solving more instances with significant reductions in both computation time and search space. These results highlight the practical effectiveness of comprehensive symmetry-aware pruning for accelerating exact MCS computation. † † cc-license: by 1. Introduction MCIS example graphs Figure 1 . Two example graphs G and H , with symmetric vertex sets \{4,5\} , \{7,9\} , and \{d,e\} . The pairs (4,5) and (7,9) exhibit negative symmetry, while (d,e) exhibit positive symmetry. The maximum common induced subgraph (MCIS) is shown in bold, with the vertex mapping M=\{(0,a),(1,b),(2,d),(3,g),(4,c),(6,j),(7,i)\} . MCIS example graphs Graphs are a powerful tool for representing structured data and are widely used in diverse application domains. For instance, computer networks are modeled with devices as vertices and communication links as edges; chemical compounds are represented as graphs where atoms and bonds correspond to vertices and edges ( 4 ; 8 ) ; and social networks model individuals and their interactions in a similar manner ( 11 ) . Identifying structural similarities in graphs is critical for tasks such as detecting anomalies in network traffic, classifying chemical compounds, and analyzing communities in social networks ( 23 ) . A well-established measure of similarity between two graphs is the Maximum Common Induced Subgraph (MCIS). The MCIS problem asks for the largest induced subgraphs of two input graphs that are isomorphic, meaning there exists a one-to-one correspondence between their vertices that preserves adjacency. Figure 1 illustrates two example graphs, G and H , with their maximum common induced subgraph shown in bold. Since MCIS is NP-hard ( 1 ) , finding exact solutions is computationally challenging, particularly for large and dense graphs. To tackle the MCIS problem, a variety of algorithmic strategies have been explored, including constraint programming approaches ( 24 ; 18 ) , clique-based formulations ( 12 ; 9 ; 2 ) , and backtracking-based search algorithms ( 17 ; 16 ) . Among the most effective exact methods is the McSplit algorithm, a branch-and-bound (BnB) approach that systematically explores the space of partial vertex mappings using a depth-first search strategy ( 16 ) . McSplit partitions candidate vertex pairs into bidomains , each representing subsets of vertices from G and H that remain feasible for matching under the current mapping. It then applies a bounding rule to estimate the largest possible extension of the current mapping, allowing early pruning of branches that cannot lead to an optimal solution. Building on McSplit, the recently proposed RRSplit algorithm ( 25 ) improves efficiency by introducing vertex-equivalence-based pruning and a refined upper bound that better reflects local structural redundancy. By grouping structurally equivalent vertices into equivalence classes, RRSplit avoids redundant exploration of symmetric subtrees and achieves notable performance gains. However, its treatment of symmetry remains limited: the equivalence reasoning applies only within one input graph and does not account for the symmetries that arise from both input graphs. For example, in fig. 1 , the vertices in graph G that share identical neighborhoods are \{4,5\} and \{7,9\} , while in H , the corresponding pair is \{d,e\} . For instance, in a common subgraph containing at least one of vertices 4 and 5 , swapping them produces a symmetric solution. RRSplit detects and avoids revisiting such redundant cases. However, swapping vertices \{d,e\} in H also produces symmetric solutions, provided at least one of them is contained in the common subgraph. Such redundant cases caused by equivalent vertices in H are missed by RRSplit, whereas our proposed method accounts for symmetries in both input graphs, G and H . While this seems straight-forward conceptually, these symmetries can interact, making correctness and efficient detection/avoidance non-trivial issues. In the broader context of constraint programming, the two input graphs in an MCIS instance are often referred to as the variable graph and the value graph . Vertices in the variable graph are treated as variables to be assigned, while vertices in the value graph, along with a special symbol representing unmatched vertices, serve as possible values. The objective of an MCIS algorithm is to assign values to variables so that the induced subgraphs of the variable and value graphs are isomorphic and no other mapping includes more vertices. This perspective highlights the asymmetric yet interdependent roles of the two graphs and motivates the need for symmetry breaking strategies that operate coherently across both. To address these limitations, we propose a novel algorithm called SymSplit , which systematically eliminates redundant exploration by breaking symmetries arising from similar neighborhoods in both the variable and value graphs. At the core of our approach lies a dual-symmetry breaking framework that preserves the exactness of the algorithm while substantially improving efficiency. SymSplit identifies symmetric structures in the input graphs and prunes equivalent search branches that correspond to the same subgraph mappings. By avoiding these unnecessary explorations, the proposed method significantly reduces computation time without compromising completeness or correctness. Contributions. The main contributions of this work are summarized as follows: • We present a principled framework for detecting and eliminating symmetric branches during the search by identifying structurally equivalent vertices with identical neighborhoods in both input graphs. The framework unifies two complementary techniques: variable symmetry breaking and value symmetry breaking that together provide more complete symmetry elimination for the MCIS problem. • We design an efficient and lightweight method for detecting relevant graph symmetries that minimizes computational overhead. Our implementation ensures that the symmetry detection process scales effectively to large graph instances, making the approach practical for real-world applications. • We formally establish the correctness and completeness of the proposed framework, proving that variable and value symmetry breaking can be applied simultaneously without interference. Our proofs extend to directed graphs and graphs with self-loops. We also analyze the computational complexity of symmetry identification and computation. • We perform extensive experiments on standard MCIS benchmark datasets to assess the effectiveness of our approach. The results show that SymSplit consistently solves more problem instances in less time compared to state-of-the-art algorithms, demonstrating the practical benefits of comprehensive symmetry breaking in exact MCIS computation. 2. State-of-the-art Solutions

Read the complete text