Aug 2026· Match-communications in Mathematical and in Computer Chemistry· Vol 97 (2027), pp. 821· 0 citations· 26 references
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.
It is proved that both the maximum common edge subgraph and the graph edit distance remain NP-hard, even when both graphs are paths, even when one graph is a path and the other is a tree.
Maximilian Limmer, Nils M. Kriege· arXiv.org· 0 citations
The cost of a hierarchical clustering can be represented by an ultrametric whose lowest-common-ancestor labels are cluster cardinalities. We relate this known representation to the shortest-path geometry of a similarity graph. For a connected support graph $G$, let $d_G$ be its unit-length shortest-path metric and let the edge weights enter only the objective. We prove that the shifted Dasgupta optimum is exactly the minimum edge-weighted cost of a cardinality-realizable ultrametric that dominates $d_G$. Connectedification lemmas put this problem and its freely labeled dominating-ultrametric relaxation on the same class of connected binary hierarchies, labeled respectively by cardinality and graph diameter. As a sharp baseline, we determine the exact worst-case price of cardinality realizability: on every $n$-vertex instance the ratio of the two optima is at most $(2n-1)/3$, with equality on the unweighted complete graph; the sharp factor for the standard unshifted objective is $2(n+1)/3$. Our principal structural result bounds this gap by a hereditary weighted fragmentation profile defined through connected balanced cuts. Uniform local control gives an $O(\log n)$ gap, polynomial decay gives a constant gap, and the logarithmic order is tight even for unweighted trees of maximum degree $3$. On locally regular bounded-degree trees, the hierarchy can be constructed in $O(n\log n)$ time. An energy decomposition and a geometric density bound provide supporting instance-sensitive estimates. Thus the cardinality label has an unavoidable linear worst case but admits substantially smaller bounds on natural sparse graph classes.
It is shown that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order, and under the order-dependent model, where bidirectional Dijkstra is not instance-optimal.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 0 citations
Under stochastic block models, it is proved that stronger topological disruptions incur asymptotically larger distances almost surely in both inter-community and intra-community split settings.
S. Bhattacharyya, Huiyan Sang, Bani Mallick· 0 citations
We study the parameterized complexity of Induced Subgraph Isomorphism (ISI) and Maximum Common Induced Subgraph (MCIS) with respect to the cluster vertex deletion number $k$. For ISI, we give a randomized $O^*(k^{O(k)})$-time algorithm, showing that ISI is fixed-parameter tractable under this parameter and resolving an open question of Hanaka et al. [WALCOM 2026]. Our algorithm is optimal under the Exponential Time Hypothesis (ETH), and is based on a reduction to Exact Multicolored Matching solvable via algebraic techniques. For MCIS, we present a randomized $O^*(2^{O(k^2)})$-time algorithm via a reduction to a weighted variant of Exact Multicolored Matching, and we prove a matching ETH-based lower bound by showing that a $k$-by-$k$ binary matrix feasibility problem with list-constrained rows and columns admits no $O^*(2^{o(k^2)})$-time algorithm, which may be of independent interest. These results reveal that, in this setting, MCIS is strictly harder than ISI. Finally, for the three-graph variant 3-MCIS, we show that it becomes NP-hard already when each input graph has cluster vertex deletion number 2.
Tomohiro Koana, Soh Kumabe, Y. Otachi· 0 citations
This work presents a novel algorithm named HP-MC that, like prior approaches, is based on the branch and bound search, but which outperforms the leading maximum clique codes on large sparse graphs of various topologies by up to 10x on average.
Cameron Bradley, M. Burtscher· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
