The complexity of independent set reconfiguration on bipartite graphs
From MaRDI portal
(Redirected from Publication:4629977)
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
(47)- 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
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)
