Dulmage-Mendelsohn Canonical Decomposition as a generic pruning technique

We introduce a new generic propagation mechanism for constraint programming. A first advantage of our pruning technique stems from the fact that it can be applied on various global constraints. In this work we describe a filtering scheme for such a family based on Dulmage-Mendelsohn Structure Theorem. Our method checks the feasibility in polynomial time and then ensures hyper-arc consistency in linear time. It is also applicable to any soft version of global constraint expressed in terms of a maximum matching in a bipartite graph and remains of linear complexity.