Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries
Proceedings of the ACM on Management of Data · 2026-05-18 · 4 (3) · 1-26
DOI: 10.1145/3802005 ↗At a glance
Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-18. Written by Buddhi Kothalawala and 2 co-authors. 28 references. Funded by: Australian Research Council.
Abstract (original language)
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.
Funding
- Australian Research Council
Cite
APA
Kothalawala, B., Koehler, H., & Farhan, M. (2026). Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries. Proceedings of the ACM on Management of Data, 4(3), 1-26. https://doi.org/10.1145/3802005
Vancouver
Kothalawala B, Koehler H, Farhan M. Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries. Proceedings of the ACM on Management of Data. 2026;4(3):1-26. doi:10.1145/3802005
BibTeX
@article{Kothalawala2026,
author = {Kothalawala, Buddhi and Koehler, Henning and Farhan, Muhammad},
title = {Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--26},
doi = {10.1145/3802005}
}
EUVIMED