### Abstract

We present a polynomial-time algorithm that, given two independent sets in a claw-free graph G, decides whether one can be transformed into the other by a sequence of elementary steps. Each elementary step is to remove a vertex v from the current independent set S and to add a new vertex w (not in S) such that the result is again an independent set. We also consider the more restricted model where v and w have to be adjacent.

Original language | Undefined |
---|---|

Title of host publication | Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014 |

Editors | R. Ravi, Inge Li Gørtz |

Place of Publication | Switzerland |

Publisher | Springer |

Pages | 86-97 |

Number of pages | 12 |

ISBN (Print) | 978-3-319-08403-9 |

DOIs | |

Publication status | Published - Jul 2014 |

Event | 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014 - Copenhagen , Denmark Duration: 2 Jul 2014 → 4 Jul 2014 Conference number: 14 http://algolog.compute.dtu.dk/swat2014/ |

### Publication series

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

Publisher | Springer International Publishing |

Volume | 8503 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014 |
---|---|

Abbreviated title | SWAT 2014 |

Country | Denmark |

City | Copenhagen |

Period | 2/07/14 → 4/07/14 |

Internet address |

### Keywords

- EWI-25463
- Reconfiguration
- Token Sliding
- METIS-309751
- IR-93932
- Claw-free graph
- Graph algorithms

## Cite this

Bonsma, P. S., Kamiński, M., & Wrochna, M. (2014). Reconfiguring Independent Sets in Claw-Free Graphs. In R. Ravi, & I. L. Gørtz (Eds.),

*Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014*(pp. 86-97). (Lecture Notes in Computer Science; Vol. 8503). Switzerland: Springer. https://doi.org/10.1007/978-3-319-08404-6_8