EUVIMEDEUVIMED entdecken
Crossref

Biclique reconfiguration in bipartite graphs

Yota Otachi, Emi Toyoda

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →