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 -