EUVIMEDEUVIMED entdecken
Crossref

Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries

Buddhi Kothalawala, Henning Koehler, Muhammad Farhan

Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-26

DOI: 10.1145/3802005 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Buddhi Kothalawala und 2 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Gefördert von: Australian Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Australian Research Council

Zitieren

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}
}
Kostenlos starten →