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 problem of finding a tangle that realizes a given list~$L$ 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 $n$ wires and a given list~$L$ of swaps in $O((2|L|/n^2+1)^{ n^2/2} \cdot \varphi^n \cdot n)$ time, where $\varphi \approx 1.618$ is the golden ratio and $|L|$ is the total number of swaps in~$L$. 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 $O(n!\varphi^n)$ time.

Categories: cs.CG cs.DM cs.DS

Deciding the Feasibility and Minimizing the Height of Tangles