Learning to Bound for Maximum Common Subgraph Algorithms

Identifying the maximum common subgraph between two graphs is a computationally challenging NP-hard problem. While the McSplit algorithm represents a state-of-the-art approach within a branch-and-bound (BnB) framework, several extensions have been proposed to enhance its vertex pair selection strategy, often utilizing reinforcement learning techniques. Nonetheless, the quality of the upper bound remains a critical factor in accelerating the search process by effectively pruning unpromising branches. This research introduces a novel, more restrictive upper bound derived from a detailed analysis of the McSplit algorithm's generated partitions. To enhance the effectiveness of this bound, we propose a reinforcement learning approach that strategically directs computational effort towards the most promising regions within the search space.

Keywords

Combinatorial Search, Branch and Bound, Graph Theory

Citation

Kothalawala BW, Koehler H, Wang Q. (2025). Learning to Bound for Maximum Common Subgraph Algorithms. Garcia de la Banda M. Leibniz International Proceedings in Informatics Lipics. (pp. 22:1-22:18). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany.

URI

https://mro.massey.ac.nz/handle/10179/73420

Collections

Conference Papers

Full item page