Logo

Download

Title:
Exact Enumeration of All Connected Maximum Common Subgraphs in Multiple Labeled Graphs: Application to Cheminformatics
Authors:
Johannes B. S. Petersen ORCID iD 0009-0004-0079-5189
Akbar Davoodi ORCID iD 0000-0001-6403-5091
Thomas Gärtner ORCID iD 0000-0001-5985-9213
Marc Hellmuth ORCID iD 0000-0002-1620-5508
Daniel Merkle ORCID iD 0000-0001-7792-375X
Volume
97
Issue
3
Year
2027
Pages
821-870
Abstract

We present an exact algorithmic framework for enumerating all maximum common subgraphs shared by multiple vertex- and edge-labeled graphs, motivated by molecular-graph comparison in cheminformatics and computational chemistry and, more generally, by comparison problems on labeled networks. The framework addresses maximum common induced subgraphs (MCIS), maximum common edge subgraphs (MCES), and their connected variants under label-preserving matching. Algorithmically, it combines labeled modular-product constructions with a modified Bron-Kerbosch clique-enumeration procedure that retains the maximal intermediate candidates needed for exact multi-graph reduction. To improve practical performance, we incorporate pruning of redundant type-0 product edges and similarity-based ordering of the input graphs. Formal correctness proofs, benchmarks on the ZINC and ChEMBL22 molecular datasets, and a publicly available implementation show that the framework yields a reproducible exact method for labeled-network comparison that is practically usable on the studied molecular instance sizes.