A Backtracking Algorithmic Toolbox for Solving the Subgraph Isomorphism Problem

Abstract

The subgraph isomorphism problem asks whether a given graph is a subgraph of another graph. It is one of the most general NP-complete problems since many other problems (e.g., Hamiltonian cycle, clique, independent set, etc.) have a natural reduction to subgraph isomorphism. Furthermore, there is a variety of practical applications where graph pattern matching is the core problem. Developing efficient algorithms and solvers for this problem thus enables good solutions to a variety of different practical problems. In this chapter, the authors present and experimentally explore various algorithmic refinements and code optimizations for improving the performance of subgraph isomorphism solvers. In particular, they focus on algorithms that are based on the backtracking approach and constraint satisfaction programming. They gather experiences from many state-of-the-art algorithms as well as from their engagement in this field. Lessons learned from engineering such a solver can be utilized in many other fields where backtracking is a prominent approach for solving a particular problem.