Complexity of independent set reconfigurability problems

Marcin Kamiski; Paul Medvedev; Martin Milanič

doi:10.1016/j.tcs.2012.03.004

Complexity of independent set reconfigurability problems

Marcin Kamiski, Paul Medvedev, Martin Milanič

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

134 Scopus citations

Abstract

We study problems of reconfigurability of independent sets in graphs. We consider three different models (token jumping, token sliding, and token addition and removal) and analyze relationships between them. We prove that independent set reconfigurability in perfect graphs (under any of the three models) generalizes the shortest path reconfigurability problem in general graphs and is therefore PSPACE-complete. On the positive side, we give polynomial results for even-hole-free graphs and ^P4-free graphs.

Original language	English (US)
Pages (from-to)	9-15
Number of pages	7
Journal	Theoretical Computer Science
Volume	439
DOIs	https://doi.org/10.1016/j.tcs.2012.03.004
State	Published - Jun 29 2012

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2012.03.004

Cite this

@article{2fc5dfe2954e4988aa958d3a6e6cfed9,

title = "Complexity of independent set reconfigurability problems",

abstract = "We study problems of reconfigurability of independent sets in graphs. We consider three different models (token jumping, token sliding, and token addition and removal) and analyze relationships between them. We prove that independent set reconfigurability in perfect graphs (under any of the three models) generalizes the shortest path reconfigurability problem in general graphs and is therefore PSPACE-complete. On the positive side, we give polynomial results for even-hole-free graphs and P4-free graphs.",

author = "Marcin Kamiski and Paul Medvedev and Martin Milani{\v c}",

year = "2012",

month = jun,

day = "29",

doi = "10.1016/j.tcs.2012.03.004",

language = "English (US)",

volume = "439",

pages = "9--15",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Complexity of independent set reconfigurability problems

AU - Kamiski, Marcin

AU - Medvedev, Paul

AU - Milanič, Martin

PY - 2012/6/29

Y1 - 2012/6/29

N2 - We study problems of reconfigurability of independent sets in graphs. We consider three different models (token jumping, token sliding, and token addition and removal) and analyze relationships between them. We prove that independent set reconfigurability in perfect graphs (under any of the three models) generalizes the shortest path reconfigurability problem in general graphs and is therefore PSPACE-complete. On the positive side, we give polynomial results for even-hole-free graphs and P4-free graphs.

AB - We study problems of reconfigurability of independent sets in graphs. We consider three different models (token jumping, token sliding, and token addition and removal) and analyze relationships between them. We prove that independent set reconfigurability in perfect graphs (under any of the three models) generalizes the shortest path reconfigurability problem in general graphs and is therefore PSPACE-complete. On the positive side, we give polynomial results for even-hole-free graphs and P4-free graphs.

UR - http://www.scopus.com/inward/record.url?scp=84861234762&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84861234762&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2012.03.004

DO - 10.1016/j.tcs.2012.03.004

M3 - Article

AN - SCOPUS:84861234762

SN - 0304-3975

VL - 439

SP - 9

EP - 15

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Complexity of independent set reconfigurability problems

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this