Kothalawala BWKoehler HWang QGarcia de la Banda M2025-08-262025-08-262025-08-08Kothalawala 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.1868-8969https://mro.massey.ac.nz/handle/10179/73420Identifying 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.(c) 2025 The Author/sCC BY 4.0https://creativecommons.org/licenses/by/4.0/Combinatorial SearchBranch and BoundGraph Theoryconference10.4230/LIPIcs.CP.2025.22c-conference-paper-in-proceedings22:1-22:18