Biclique Reconfiguration in Bipartite Graphs
This resolves an open problem in computational complexity theory for graph reconfiguration problems, though it appears incremental as it builds on prior NP-hardness results.
The authors proved that Balanced Biclique Reconfiguration on bipartite graphs is PSPACE-complete, which resolved an open problem about Connected Components Reconfiguration being PSPACE-complete under all studied rules.
We prove that Balanced Biclique Reconfiguration on bipartite graphs is PSPACE-complete. This implies the PSPACE-completeness of the spanning variant of Subgraph Reconfiguration under the token jumping rule for the property "a graph is an $(i, j)$-complete bipartite graph," which was previously known only to be NP-hard [Hanaka et al. TCS 2020]. Using our result, we also show that Connected Components Reconfiguration with two connected components is PSPACE-complete under all previously studied rules, resolving an open problem of Nakahata [COCOON 2025] in the negative.