Constraint Satisfaction Problems: Convexity makes all Different constraints tractable

Michael Fellows; Tobias Friedrich; Danny Hermelin; Nina Narodytska; Frances Rosamond

Constraint Satisfaction Problems: Convexity makes all Different constraints tractable

Michael Fellows, Tobias Friedrich, Danny Hermelin, Nina Narodytska, Frances Rosamond

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

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.

Original language	English
Title of host publication	Proceedings of the 22nd International Joint conference on Artificial Intelligence
Editors	Toby Walsh
Place of Publication	California
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	522-527
Number of pages	6
ISBN (Print)	978-1-57735-516-8
Publication status	Published - 2011
Event	International Joint Conference on Artificial Intelligence (IJCAI 2011 22nd) - Barcelona, Spain, Barcelona, Spain Duration: 19 Jul 2011 → 22 Jul 2011 Conference number: 2011 (22nd)

Conference

Conference	International Joint Conference on Artificial Intelligence (IJCAI 2011 22nd)
Abbreviated title	IJCAI
Country/Territory	Spain
City	Barcelona
Period	19/07/11 → 22/07/11

Cite this

@inproceedings{2263035ac1e94b1291c0f206fc97c1e6,

title = "Constraint Satisfaction Problems: Convexity makes all Different constraints tractable",

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.",

author = "Michael Fellows and Tobias Friedrich and Danny Hermelin and Nina Narodytska and Frances Rosamond",

year = "2011",

language = "English",

isbn = "978-1-57735-516-8",

pages = "522--527",

editor = "Toby Walsh",

booktitle = "Proceedings of the 22nd International Joint conference on Artificial Intelligence",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

note = "International Joint Conference on Artificial Intelligence (IJCAI 2011 22nd), IJCAI ; Conference date: 19-07-2011 Through 22-07-2011",

}

Fellows, M, Friedrich, T, Hermelin, D, Narodytska, N & Rosamond, F 2011, Constraint Satisfaction Problems: Convexity makes all Different constraints tractable. in T Walsh (ed.), Proceedings of the 22nd International Joint conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence (AAAI), California, pp. 522-527, International Joint Conference on Artificial Intelligence (IJCAI 2011 22nd), Barcelona, Spain, 19/07/11.

Constraint Satisfaction Problems: Convexity makes all Different constraints tractable. / Fellows, Michael; Friedrich, Tobias; Hermelin, Danny et al.
Proceedings of the 22nd International Joint conference on Artificial Intelligence. ed. / Toby Walsh. California: Association for the Advancement of Artificial Intelligence (AAAI), 2011. p. 522-527.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

TY - GEN

T1 - Constraint Satisfaction Problems

T2 - International Joint Conference on Artificial Intelligence (IJCAI 2011 22nd)

AU - Fellows, Michael

AU - Friedrich, Tobias

AU - Hermelin, Danny

AU - Narodytska, Nina

AU - Rosamond, Frances

N1 - Conference code: 2011 (22nd)

PY - 2011

Y1 - 2011

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

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

UR - http://ijcai-11.iiia.csic.es/

UR - http://www.ijcai.org/proceedings/2011

M3 - Conference Paper published in Proceedings

SN - 978-1-57735-516-8

SP - 522

EP - 527

BT - Proceedings of the 22nd International Joint conference on Artificial Intelligence

A2 - Walsh, Toby

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - California

Y2 - 19 July 2011 through 22 July 2011

ER -

Constraint Satisfaction Problems: Convexity makes all Different constraints tractable

Abstract

Conference

Other files and links

Fingerprint

Cite this