Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable

Fellows, Michael R.; Friedrich, Tobias; Hermelin, Danny; Narodytska, Nina; Rosamond, Frances A.

doi:10.5591/978-1-57735-516-8/IJCAI11-095

Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable

Michael R. Fellows, Tobias Friedrich, Danny Hermelin, Nina Narodytska, Frances A. Rosamond

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 522-526.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-095

Abstract

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 while it is provably intractable in general.

Michael R. Fellows, Tobias Friedrich, Danny Hermelin, Nina Narodytska, and Frances A. Rosamond. 2011. Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 522–526. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-095

@inproceedings{ijcai2011p95,
  title     = {Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable},
  author    = {Fellows, Michael R. and Friedrich, Tobias and Hermelin, Danny and Narodytska, Nina and Rosamond, Frances A.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {522--526},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-095},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-095},
}

TY  - CPAPER
TI  - Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable
AU  - Fellows, Michael R.
AU  - Friedrich, Tobias
AU  - Hermelin, Danny
AU  - Narodytska, Nina
AU  - Rosamond, Frances A.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 522
EP  - 526
DO  - 10.5591/978-1-57735-516-8/IJCAI11-095
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-095
ER  -