### 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 language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science |

Subtitle of host publication | 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers |

Editors | Dieter Kratsch, Ioan Todinca |

Place of Publication | Cham, Switzerland |

Publisher | Springer |

Pages | 105-116 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-319-12340-0 |

ISBN (Print) | 978-3-319-12339-4 |

DOIs | |

Publication status | Published - Jun 2014 |

Event | 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014 - Nouan-le-Fuzelier, France Duration: 25 Jun 2014 → 27 Jun 2014 Conference number: 40 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer International Publishing |

Volume | 8747 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014 |
---|---|

Abbreviated title | WG |

Country | France |

City | Nouan-le-Fuzelier |

Period | 25/06/14 → 27/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