2022/08/18 by Yanli Liu, Jiming Zhao, Liu, Yanli +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Artificial Intelligence (cs.AI) #Cancer-related gene regulation #FOS: Computer and information sciences #Protein Degradation and Inhibitors #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.2208.08620
openalex publication_date 2022/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Maximum Common induced Subgraph (MCS) is an important NP-hard problem with wide real-world applications. Branch-and-Bound (BnB) is the basis of a class of efficient algorithms for MCS, consisting in successively selecting vertices to match and pruning when it is discovered that a solution better than the best solution found so far does not exist. The method of selecting the vertices to match is essential for the performance of BnB. In this paper, we propose a new value function and a hybrid selection strategy used in reinforcement learning to define a new vertex selection method, and propose a new BnB algorithm, called McSplitDAL, for MCS. Extensive experiments show that McSplitDAL significantly improves the current best BnB algorithms, McSplit+LL and McSplit+RL. An empirical analysis is also performed to illustrate why the new value function and the hybrid selection strategy are effective.