Independent Set Reconfiguration in Cographs

P.S. Bonsma

doi:10.1007/978-3-319-12340-0_9

Independent Set Reconfiguration in Cographs

P.S. Bonsma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

10 Citations (Scopus)

7 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 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	https://doi.org/10.1007/978-3-319-12340-0_9
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

Access to Document

10.1007/978-3-319-12340-0_9

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). Springer. https://doi.org/10.1007/978-3-319-12340-0_9

@inproceedings{eba8520c942a4762a9deccd612ed896e,

title = "Independent Set Reconfiguration in Cographs",

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.",

keywords = "graph classes, Reconfiguration, token jumping, METIS-309752, cograph, Graph algorithms, IR-93933, EWI-25464",

author = "P.S. Bonsma",

note = "eemcs-eprint-25464 ; 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, WG ; Conference date: 25-06-2014 Through 27-06-2014",

year = "2014",

month = jun,

doi = "10.1007/978-3-319-12340-0\_9",

language = "English",

isbn = "978-3-319-12339-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "105--116",

editor = "Dieter Kratsch and Ioan Todinca",

booktitle = "Graph-Theoretic Concepts in Computer Science",

address = "Germany",

}

Bonsma, PS 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. Lecture Notes in Computer Science, vol. 8747, Springer, Cham, Switzerland, pp. 105-116, 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, Nouan-le-Fuzelier, France, 25/06/14. https://doi.org/10.1007/978-3-319-12340-0_9

Independent Set Reconfiguration in Cographs. / Bonsma, P.S.
Graph-Theoretic Concepts in Computer Science: 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers. ed. / Dieter Kratsch; Ioan Todinca. Cham, Switzerland: Springer, 2014. p. 105-116 (Lecture Notes in Computer Science; Vol. 8747).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Independent Set Reconfiguration in Cographs

AU - Bonsma, P.S.

N1 - Conference code: 40

PY - 2014/6

Y1 - 2014/6

N2 - 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.

AB - 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.

KW - graph classes

KW - Reconfiguration

KW - token jumping

KW - METIS-309752

KW - cograph

KW - Graph algorithms

KW - IR-93933

KW - EWI-25464

U2 - 10.1007/978-3-319-12340-0_9

DO - 10.1007/978-3-319-12340-0_9

M3 - Conference contribution

SN - 978-3-319-12339-4

T3 - Lecture Notes in Computer Science

SP - 105

EP - 116

BT - Graph-Theoretic Concepts in Computer Science

A2 - Kratsch, Dieter

A2 - Todinca, Ioan

PB - Springer

CY - Cham, Switzerland

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

Y2 - 25 June 2014 through 27 June 2014

ER -

Independent Set Reconfiguration in Cographs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this