Reconfiguration problems

Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria.

Download
OA THESIS_Zuzka_Masarova.pdf 13.66 MB [Published Version]

Thesis | PhD | Published | English
Series Title
ISTA Thesis
Abstract
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.
Publishing Year
Date Published
2020-06-09
Publisher
Institute of Science and Technology Austria
Page
160
ISSN
IST-REx-ID

Cite this

Masárová Z. Reconfiguration problems. 2020. doi:10.15479/AT:ISTA:7944
Masárová, Z. (2020). Reconfiguration problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7944
Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7944.
Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology Austria, 2020.
Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria.
Masárová, Zuzana. Reconfiguration Problems. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7944.
All files available under the following license(s):
Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2020-06-08
MD5 Checksum
df688bc5a82b50baee0b99d25fc7b7f0

Source File
Access Level
Restricted Closed Access
Date Uploaded
2020-06-08
MD5 Checksum
45341a35b8f5529c74010b7af43ac188

Material in ISTA:
Part of this Dissertation
Part of this Dissertation

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search