Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (6): 1756-1760.

Special Issue: 先进计算

### Maximum common induced subgraph algorithm based on vertex conflict learning

WANG Yu1, LIU Yanli1,2, CHEN Shaowu1

1. 1. College of Science, Wuhan University of Science and Technology, Wuhan Hubei 430081, China;
2. Hubei Province Key Laboratory of Systems Science in Metallurgical Process(Wuhan University of Science and Technology), Wuhan Hubei 430081, China
• Received:2020-09-07 Revised:2020-11-02 Online:2021-06-10 Published:2020-11-16
• Supported by:
This work is partially supported by the Innovative Training Program for College Students of Hubei (S201910488044), the Open Funds of Hubei Province Key Laboratory of Systems Science in Metallurgical Process (Y201716).

### 基于顶点冲突学习的最大公共子图算法

1. 1. 武汉科技大学 理学院, 武汉 430081;
2. 冶金工业过程系统科学湖北省重点实验室(武汉科技大学), 武汉 430081
• 通讯作者: 刘燕丽
• 作者简介:王宇(1999-),男,湖北汉川人,主要研究方向:最大公共子图问题;刘燕丽(1980-),女,河南西平人,副教授,博士,CCF会员,主要研究方向:组合优化问题求解、算法设计;陈劭武(1999-),男,湖北武汉人,主要研究方向:最大公共子图问题。
• 基金资助:
湖北省大学生创新训练项目（S201910488044）；冶金工业过程系统科学湖北重点实验室开放基金资助项目（Y201716）。

Abstract: The traditional branching strategies of Maximum Common induced Subgraph (MCS) problem rely on the static properties of graphs and lack learning information about historical searches. In order to solve these problems, a branching strategy based on vertex conflict learning was proposed. Firstly, the reduction value of the upper bound was used as the reward to the branch node for completing a matching action. Secondly, when the optimal solution was updated, the optimal solution obtained actually was the result of continuous inference of the branch nodes. Therefore, the appropriate rewards were given to the branch nodes on the complete search path to strengthen the positive effect of these vertices on search. Finally, the value function of matching action was designed, and the vertices with the maximum cumulative rewards would be selected as new branch nodes. On the basis of Maximum common induced subgraph Split (McSplit) algorithm, an improved McSplit Reinforcement Learning and Routing (McSplitRLR) algorithm combined with the new branching strategy was completed. Experimental results show that, with the same computer and solution time limit, excluding the simple instances solved by all comparison algorithms within 10 seconds, compared to the state-of-the-art algorithms of McSplit and McSplit Solution-Biased Search (McSplitSBS), McSplitRLR solves 109 and 33 more hard instances respectively, and the solution rate increases by 5.6% and 1.6% respectively.

CLC Number: