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 proceedingConference Paper published in Proceedingspeer-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 languageEnglish
    Title of host publicationProceedings of the 22nd International Joint conference on Artificial Intelligence
    EditorsToby Walsh
    Place of PublicationCalifornia
    PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
    Pages522-527
    Number of pages6
    ISBN (Print)978-1-57735-516-8
    Publication statusPublished - 2011
    EventInternational Joint Conference on Artificial Intelligence (IJCAI 2011 22nd) - Barcelona, Spain, Barcelona, Spain
    Duration: 19 Jul 201122 Jul 2011
    Conference number: 2011 (22nd)

    Conference

    ConferenceInternational Joint Conference on Artificial Intelligence (IJCAI 2011 22nd)
    Abbreviated titleIJCAI
    CountrySpain
    CityBarcelona
    Period19/07/1122/07/11

    Fingerprint

    Dive into the research topics of 'Constraint Satisfaction Problems: Convexity makes all Different constraints tractable'. Together they form a unique fingerprint.

    Cite this