PathLAD+: An Improved Exact Algorithm for Subgraph Isomorphism Problem

The subgraph isomorphism problem (SIP) is a challenging problem with wide practical applications. In the last decade, despite being a theoretical hard problem, researchers design various algorithms for solving SIP. In this work, we propose three main heuristics and develop an improved exact algorithm for SIP. First, we design a probing search procedure to try whether the search procedure can successfully obtain a solution at first sight. Second, we design a novel matching ordering as a value-ordering heuristic, which uses some useful information obtained from the probing search procedure to preferentially select some promising target vertices. Third, we discuss the characteristics of different propagation methods in the context of SIP and present an adaptive propagation method to make a good balance between these methods. Experimental results on a broad range of real-world benchmarks show that our proposed algorithm performs better than state-of-the-art algorithms for the SIP.

Authors

• Yiyuan Wang Northeast Normal University
• Chenghou Jin Fudan University
• Shaowei Cai Institute of Software, Chinese Academy of Sciences
• Qingwei Lin Microsoft Research

Keywords

• Search: S: Combinatorial search and optimisation
• Search: S: Heuristic search