The complexity of independent set reconfiguration on bipartite graphs
classification
💻 cs.CC
cs.DM
keywords
problemreconfigurationtokenbipartitecomplexitygraphsindependentmodel
read the original abstract
We settle the complexity of the Independent Set Reconfiguration problem on bipartite graphs under all three commonly studied reconfiguration models. We show that under the token jumping or token addition/removal model the problem is NP-complete. For the token sliding model, we show that the problem remains PSPACE-complete.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.