The complexity of independent set reconfiguration on bipartite graphs
From MaRDI portal
(Redirected from The complexity of independent set reconfiguration on bipartite graphs)
The complexity of independent set reconfiguration on bipartite graphs (scientific article; zbMATH DE number 7044611)
The complexity of independent set reconfiguration on bipartite graphs (scientific article; zbMATH DE number 7044611)
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.
Recommendations
Cited in
(49)- On girth and the parameterized complexity of token sliding and token jumping
- On reconfigurability of target sets
- Invitation to combinatorial reconfiguration
- Reconfiguration of regular induced subgraphs
- Parameterized complexity of reconfiguration of atoms
- Parameterized complexity of independent set reconfiguration problems
- Can local optimality be used for efficient data reduction?
- Reconfiguration of cliques in a graph
- Computing \(k\)-independent sets for regular bipartite graphs
- Complexity of independent set reconfigurability problems
- The complexity of independent set reconfiguration on bipartite graphs
- Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
- Token sliding on split graphs
- Token sliding on graphs of girth five
- Feedback vertex set reconfiguration in planar graphs
- scientific article; zbMATH DE number 7765402 (Why is no real title available?)
- On the complexity of distance-\(d\) independent set reconfiguration
- Galactic token sliding
- Extremal independent set reconfiguration
- Reconfiguring Independent Sets on Interval Graphs
- Token sliding on graphs of girth five
- On the complexity of distance-\(d\) independent set reconfiguration
- Minimum separator reconfiguration
- Parameterized complexity of reconfiguration of atoms
- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- On finding short reconfiguration sequences between independent sets
- Bipartite independent set reconfiguration: general and RNA-inspired parameterized algorithms
- Gap preserving reductions between reconfiguration problems
- Independent set reconfiguration under bounded-hop token jumping
- Changing induced subgraph isomorphisms under extended reconfiguration rules
- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- Galactic token sliding
- Independent set reconfiguration in H-free graphs
- Changing induced subgraph isomorphisms under extended reconfiguration rules
- Reconfiguration using generalized token jumping
- Independent set reconfiguration under bounded-hop token jumping
- Some results on vertex separator reconfiguration
- Can local optimality be used for efficient data reduction?
- A survey on the parameterized complexity of reconfiguration problems
- Independent set reconfiguration on directed graphs
- Parameterized complexities of dominating and independent set reconfiguration
- Biclique reconfiguration in bipartite graphs
- Token sliding reconfiguration on DAGs
- The tape reconfiguration problem and its consequences for dominating set reconfiguration
- Coloring reconfiguration under color swapping
- Reachability of independent sets and vertex covers under extended reconfiguration rules
- Token sliding independent set reconfiguration on block graphs
- Multi-stage selection under bounded variation
- Yet another simple proof of the PCRP theorem
This page was built for publication: The complexity of independent set reconfiguration on bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629977)
