Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable
Michael Fellows, Tobias Friedrich, Danny Hermelin, Nina Narodytska and Frances Rosamond
We examine the complexity of constraint satisfaction problems (CSP) that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like time-tabling, frequency allocations and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of these Multiple AllDiff CSPs for a set natural parameters, like maximum domain size and maximum size of constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable while it is provably intractable in general.