2026-07-23T07:03:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11023 2024-03-06T10:47:04Z ddc:004 open_access

Reconfiguration of Minimum Steiner Trees via Vertex Exchanges Mizuta, Haruka Hatanaka, Tatsuhiko Ito, Takehiro Zhou, Xiao Combinatorial reconfiguration Graph algorithms Steiner tree In this paper, we study the problem of deciding if there is a transformation between two given minimum Steiner trees of an unweighted graph such that each transformation step respects a prescribed reconfiguration rule and results in another minimum Steiner tree of the graph. We consider two reconfiguration rules, both of which exchange a single vertex at a time, and generalize the known reconfiguration problem for shortest paths in an unweighted graph. This generalization implies that our problems under both reconfiguration rules are PSPACE-complete for bipartite graphs. We thus study the problems with respect to graph classes, and give some boundaries between the polynomial-time solvable and PSPACE-complete cases. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haruka Mizuta and Tatsuhiko Hatanaka and Takehiro Ito and Xiao Zhou 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.79 urn:nbn:de:0030-drops-110234 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.79 eng https://creativecommons.org/licenses/by/3.0/legalcode