Exact Enumeration of All Connected Maximum Common Subgraphs in Multiple Labeled Graphs: Application to Cheminformatics

Abstract

We present an exact algorithmic framework for enumerating all maximum common subgraphs shared by multiple vertex- and edgelabeled 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 labelpreserving 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.