AllDifferent-based filtering for subgraph isomorphism

摘要

The subgraph isomorphism problem involves deciding if there exists a copy of a pattern graph in a target graph. This problem may be solved by a complete tree search combined with filtering techniques that aim at pruning branches that do not contain solutions. We introduce a new filtering algorithm based on local all different constraints. We show that this filtering is stronger than other existing filterings — i.e., it prunes more branches — and that it is also more efficient — i.e., it allows one to solve more instances quicker.