Deciding the Feasibility and Minimizing the Height of Tangles

Abstract

We study the following combinatorial problem. Given a set of $n$ y-monotone Jordan curves, called wires, a tangle determines the order of the wires on a number of horizontal 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 swaps (that is, unordered pairs of wires) and an initial order of the wires, a tangle realizes $L$ if each pair of wires changes its order exactly as many times as specified by $L$. List-Feasibility is the problem of finding a tangle that realizes a given list $L$ for a prescribed initial order if such a tangle exists. The Tangle-Height Minimization problem additionally aims to find a tangle that uses the minimum number of layers. List-Feasibility (and therefore Tangle-Height Minimization) is NP-hard [Yamanaka et al., CCCG 2018].
We prove that 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 Tangle-Height Minimization that computes an optimal tangle for $n$ wires and a given list $L$ of swaps in $O((|L|/n^2+1)^{n^2/2} \cdot \varphi^n \cdot n! \cdot n \cdot \min\{|L|,n^2\}\cdot \log|L|)$ time, where $\varphi \approx 1.618$ is the golden ratio and $|L|$ is the total number of swaps
in $L$.
Obviously, this algorithm solves List-Feasibility, too. We show that List-Feasibility can also be solved by a simpler and faster version of the algorithm. Moreover, the algorithm helps us to show that List-Feasibility is in NP and fixed-parameter tractable with respect to the number of wires. For simple lists, where every swap occurs at most once, we show how to solve Tangle-Height Minimization in $O(n!\varphi^n)$ time.