A Strengthened Branch and Bound Algorithm for the Maximum Common (Connected) Subgraph Problem

A Strengthened Branch and Bound Algorithm for the Maximum Common (Connected) Subgraph Problem

Jianrong Zhou, Kun He, Jiongzhi Zheng, Chu-Min Li, Yanli Liu

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 1908-1914. https://doi.org/10.24963/ijcai.2022/265

We propose a new and strengthened Branch-and-Bound (BnB) algorithm for the maximum common (connected) induced subgraph problem based on two new operators, Long-Short Memory (LSM) and Leaf vertex Union Match (LUM). Given two graphs for which we search for the maximum common (connected) induced subgraph, the first operator of LSM maintains a score for the branching node using the short-term reward of each vertex of the first graph and the long-term reward of each vertex pair of the two graphs. In this way, the BnB process learns to reduce the search tree size significantly and boost the algorithm performance. The second operator of LUM further improves the performance by simultaneously matching the leaf vertices connected to the current matched vertices, and allows the algorithm to match multiple vertex pairs without affecting the optimality of solution. We incorporate the two operators into the state-of-the-art BnB algorithm McSplit, and denote the resulting algorithm as McSplit+LL. Experiments show that McSplit+LL outperforms McSplit+RL, a more recent variant of McSplit using reinforcement learning that is superior than McSplit.
Keywords:
Constraint Satisfaction and Optimization: Constraint Optimization
Constraint Satisfaction and Optimization: Solvers and Tools