Independent Set Reconfiguration in Cographs

P.S. Bonsma

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

    10 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    We study the following independent set reconfiguration problem: given two independent sets I and J of a graph G, both of size at least k, is it possible to transform I into J by adding and removing vertices one-by-one, while maintaining an independent set of size at least k throughout? This problem is known to be PSPACE-hard in general. For the case that G is a cograph on n vertices, we show that it can be solved in polynomial time. More generally, we show that for a graph class G that includes all chordal and claw-free graphs, the problem can be solved in polynomial time for graphs that can be obtained from a collection of graphs from G using disjoint union and complete join operations.
    Original languageEnglish
    Title of host publicationGraph-Theoretic Concepts in Computer Science
    Subtitle of host publication40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers
    EditorsDieter Kratsch, Ioan Todinca
    Place of PublicationCham, Switzerland
    PublisherSpringer
    Pages105-116
    Number of pages12
    ISBN (Electronic)978-3-319-12340-0
    ISBN (Print)978-3-319-12339-4
    DOIs
    Publication statusPublished - Jun 2014
    Event40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014 - Nouan-le-Fuzelier, France
    Duration: 25 Jun 201427 Jun 2014
    Conference number: 40

    Publication series

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

    Conference

    Conference40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014
    Abbreviated titleWG
    CountryFrance
    CityNouan-le-Fuzelier
    Period25/06/1427/06/14

    Keywords

    • graph classes
    • Reconfiguration
    • token jumping
    • METIS-309752
    • cograph
    • Graph algorithms
    • IR-93933
    • EWI-25464

    Fingerprint Dive into the research topics of 'Independent Set Reconfiguration in Cographs'. Together they form a unique fingerprint.

  • Cite this

    Bonsma, P. S. (2014). Independent Set Reconfiguration in Cographs. In D. Kratsch, & I. Todinca (Eds.), Graph-Theoretic Concepts in Computer Science: 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers (pp. 105-116). (Lecture Notes in Computer Science; Vol. 8747). Cham, Switzerland: Springer. https://doi.org/10.1007/978-3-319-12340-0_9