thesis
Reconfiguration problems
ISTA Thesis
published
Zuzana
Masárová
author 45CFE238-F248-11E8-B48F-1D18A9856A870000-0002-6660-1322
Uli
Wagner
supervisor
Herbert
Edelsbrunner
supervisor
HeEd
department
UlWa
department
This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures – all the triangulations of a given point set or all token placements on a given graph – can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation – by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph.
For triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton.
In the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars.
https://research-explorer.ista.ac.at/download/7944/7945/THESIS_Zuzka_Masarova.pdf
application/pdfno
https://research-explorer.ista.ac.at/download/7944/7946/THESIS_Zuzka_Masarova_SOURCE_FILES.zip
application/zip
https://creativecommons.org/licenses/by-sa/4.0/
Institute of Science and Technology Austria2020
eng
reconfigurationreconfiguration graphtriangulationsflipconstrained triangulationsshellabilitypiecewise-linear ballstoken swappingtreescoloured weighted token swapping
2663-337X
978-3-99078-005-310.15479/AT:ISTA:7944
160
https://research-explorer.ista.ac.at/record/7950 https://research-explorer.ista.ac.at/record/5986
Masárová, Zuzana. <i>Reconfiguration Problems</i>. Institute of Science and Technology Austria, 2020, doi:<a href="https://doi.org/10.15479/AT:ISTA:7944">10.15479/AT:ISTA:7944</a>.
Z. Masárová, Reconfiguration Problems, Institute of Science and Technology Austria, 2020.
Masárová, Z. (2020). <i>Reconfiguration problems</i>. Institute of Science and Technology Austria. <a href="https://doi.org/10.15479/AT:ISTA:7944">https://doi.org/10.15479/AT:ISTA:7944</a>
Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology Austria, 2020.
Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and Technology Austria, 2020. <a href="https://doi.org/10.15479/AT:ISTA:7944">https://doi.org/10.15479/AT:ISTA:7944</a>.
Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria.
Masárová Z. Reconfiguration problems. 2020. doi:<a href="https://doi.org/10.15479/AT:ISTA:7944">10.15479/AT:ISTA:7944</a>
79442020-06-08T00:49:46Z2023-09-07T13:17:37Z