Deciding the Feasibility and Minimizing the Height of Tangles

O Firman, P Kindermann, B Klemz, A Ravsky… - arXiv preprint arXiv …, 2023 - arxiv.org
O Firman, P Kindermann, B Klemz, A Ravsky, A Wolff, J Zink
arXiv preprint arXiv:2312.16213, 2023arxiv.org
We study the following combinatorial problem. Given a set of $ n $ y-monotone\emph
{wires}, a\emph {tangle} determines the order of the wires on a number of horizontal\emph
{layers} such that the orders of the wires on any two consecutive layers differ only in swaps
of neighboring wires. Given a multiset~ $ L $ of\emph {swaps}(that is, unordered pairs of
wires) and an initial order of the wires, a tangle\emph {realizes}~ $ L $ if each pair of wires
changes its order exactly as many times as specified by~ $ L $.\textsc {List-Feasibility} is the …
We study the following combinatorial problem. Given a set of y-monotone \emph{wires}, a \emph{tangle} determines the order of the wires on a number of horizontal \emph{layers} such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset~ of \emph{swaps} (that is, unordered pairs of wires) and an initial order of the wires, a tangle \emph{realizes}~ if each pair of wires changes its order exactly as many times as specified by~. \textsc{List-Feasibility} is the problem of finding a tangle that realizes a given list~ if such a tangle exists. \textsc{Tangle-Height Minimization} is the problem of finding a tangle that realizes a given list and additionally uses the minimum number of layers. \textsc{List-Feasibility} (and therefore \textsc{Tangle-Height Minimization}) is NP-hard [Yamanaka, Horiyama, Uno, Wasa; CCCG 2018]. We prove that \textsc{List-Feasibility} remains NP-hard if every pair of wires swaps only a constant number of times. On the positive side, we present an algorithm for \textsc{Tangle-Height Minimization} that computes an optimal tangle for wires and a given list~ of swaps in time, where is the golden ratio and is the total number of swaps in~. From this algorithm, we derive a simpler and faster version to solve \textsc{List-Feasibility}. We also use the algorithm to show that \textsc{List-Feasibility} is in NP and fixed-parameter tractable with respect to the number of wires. For \emph{simple} lists, where every swap occurs at most once, we show how to solve \textsc{Tangle-Height Minimization} in time.
arxiv.org