Minimizing the Height of Simple Tangles

Abstract

A tangle $T$ of height $h$ describes the ordering of $n$ elements called wires on each of $h$ levels. A pair of wires $ab$ is called a swap. Between any two adjacent levels only the ordering of adjacent wires may swap and each wire may participate in only one swap. The set of all pairs that are swapped in this way defines a multiset $S(T)$ of swaps called the swap list. A tangle $T$ realizes a given multiset $S$ of swaps if $S(T) = S$. The problem Tangle Height Minimization asks for the minimum height of a tangle that realizes $S$.

In this paper, we study the tangle height minimization problem for simple tangles, whose swap list contains each swap at most once. First, we give algorithms with running time $O(n! \cdot 1.325^n)$ and $O((n+1)!)$ space and with running time $O(1.325^{hn})$ time but $O(n^2)$ space, thereby improving over a previous algorithm that uses $O(n! \cdot 1.618^n)$ time and space. Second, we show that the simple tangle height minimization problem can be recast as a graph orientation problem and propose an integer linear program based on this formulation. In an extensive experimental evaluation that considers several variants of each approach, we demonstrate that our exponential-time algorithms and the ILP are capable of solving instances with $n \leq 60$ in a reasonable period of time. Previous approaches can only handle instances up to $n \approx 20$.