TY - JOUR

T1 - Constraint satisfaction problems

T2 - Convexity makes All Different constraints tractable

AU - Fellows, Michael

AU - Friedrich, Tobias

AU - Hermelin, Danny

AU - Narodytska, Nina

AU - Rosamond, Frances

PY - 2013/2/11

Y1 - 2013/2/11

N2 - We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, 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 Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.

AB - We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, 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 Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.

KW - AllDifferent

KW - Combinatorial problem

KW - Constraint satisfaction problems

KW - Domain size

KW - Fixed-parameter tractability

KW - Graph coloring problem

KW - NP Complete

KW - Variable domain

KW - Frequency allocation

KW - Constraint theory

UR - http://www.scopus.com/inward/record.url?scp=84873155271&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2012.11.038

DO - 10.1016/j.tcs.2012.11.038

M3 - Article

VL - 472

SP - 81

EP - 89

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -