Graph Pattern Matching using Constraint Satisfaction
Javier Larrosa, Gabriel Valiente, Gabriel Valiente · 2001
Graph pattern matching is a central problem in many application fields. Since it is NP-complete, algorithms with a good worst-case performance cannot be expected to be found. However, there is still room for general procedures with a good average performance. Using the constraint satisfaction framework, a new algorithm is presented which is superior to previous approaches. The new algorithm relies on neighborhood constraints, a constraint not used before. It is shown theoretically that the new algorithm cannot do worse than previous approaches in terms of number of visited nodes. However, since it performs more work per node, this result does not ensure that the additional effort will pay off in practice. An additional contribution is the introduction of a new benchmark for testing algorithms in this domain. It is formed by a large set of well-defined graphs of very diverse nature. In this benchmark, the new algorithm also outperforms previous approaches, while still leaving many problem instances unsolved. The use of this challenging benchmark is encouraged for future algorithms evaluation.