The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration

P.S. Bonsma, Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    31 Citations (Scopus)
    4 Downloads (Pure)

    Abstract

    In the first part of this work we study the following question: Given two k-colorings α and β of a graph G on n vertices and an integer ℓ, can α be modified into β by recoloring vertices one at a time, while maintaining a k-coloring throughout and using at most ℓ such recoloring steps? This problem is weakly PSPACE-hard for every constant k≥4. We show that the problem is also strongly NP-hard for every constant k≥4 and W[1]-hard (but in XP) when parameterized only by ℓ. On the positive side, we show that the problem is fixed-parameter tractable when parameterized by k+ℓ. In fact, we show that the more general problem of ℓ-length bounded reconfiguration of constraint satisfaction problems (CSPs) is fixed-parameter tractable parameterized by k+ℓ+r, where r is the maximum constraint arity and k is the maximum domain size. We show that for parameter ℓ, the latter problem is W[2]-hard, even for k=2. Finally, if p denotes the number of variables with different values in the two given assignments, we show that the problem is W[2]-hard when parameterized by ℓ−p, even for k=2 and r=3 .
    Original languageEnglish
    Title of host publicationProceedings of the 9th International Symposium on Parameterized and Exact Computation, IPEC 2014
    EditorsMarek Cygan, Pinar Heggernes
    Place of PublicationSwitzerland
    PublisherSpringer
    Pages110-121
    Number of pages12
    ISBN (Print)978-3-319-13523-6
    DOIs
    Publication statusPublished - Sep 2014
    Event9th International Symposium on Parameterized and Exact Computation, IPEC 2014 - Wroclaw, Poland
    Duration: 10 Sep 201412 Sep 2014

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer International Publishing
    Volume8894
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference9th International Symposium on Parameterized and Exact Computation, IPEC 2014
    Period10/09/1412/09/14
    Other10-12 September 2014

    Keywords

    • Reconfiguration
    • EWI-25462
    • Coloring
    • METIS-309750
    • Graph algorithms
    • Constraint satisfaction
    • IR-93931
    • Computational Complexity

    Fingerprint

    Dive into the research topics of 'The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration'. Together they form a unique fingerprint.

    Cite this