Scaling Subgraph Matching by Improving Ullmann Algorithm

keywords: Subgraph matching, NP-complete, graph database
Graphs are widely used to model complicated data semantics in many application domains. Subgraph isomorphism checking (an NP-complete problem) is a regular operation with this kind of data. In this paper, we propose an improvement of Ullmann algorithm, a well-known subgraph isomorphism checker. Our new algorithm is called Ullmann-ONL. It utilizes a new search ordering and L-levels of vertex neighborhoods (NL) to confine the search space of Ullmann algorithm. Our performance study shows that Ullmann-ONL outperforms previously proposed algorithms with a wide margin.
reference: Vol. 41, 2022, No. 4, pp. 1002–1024