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/Territory | 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