Biclique reconfiguration in bipartite graphs
Theoretical Computer Science · 2026-08 · 1081 · 116071
DOI: 10.1016/j.tcs.2026.116071 ↗Kurz gefasst
Fachartikel in der Zeitschrift Theoretical Computer Science, 2026-08. Verfasst von Yota Otachi und 1 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Gefördert von: Japan Society for the Promotion of Science.
Abstract (Originalsprache)
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.
Förderung
- Japan Society for the Promotion of Science
Zitieren
APA
Otachi, Y., & Toyoda, E. (2026). Biclique reconfiguration in bipartite graphs. Theoretical Computer Science, 1081, 116071. https://doi.org/10.1016/j.tcs.2026.116071
Vancouver
Otachi Y, Toyoda E. Biclique reconfiguration in bipartite graphs. Theoretical Computer Science. 2026;1081:116071. doi:10.1016/j.tcs.2026.116071
BibTeX
@article{Otachi2026,
author = {Otachi, Yota and Toyoda, Emi},
title = {Biclique reconfiguration in bipartite graphs},
journal = {Theoretical Computer Science},
year = {2026},
volume = {1081},
pages = {116071},
doi = {10.1016/j.tcs.2026.116071}
}
EUVIMED