Introduction: Exploring the Complexity of Combinatorial Problems with Wires and Swaps
In this article, we delve into the intricacies of a combinatorial problem involving y-monotone wires. The problem revolves around the concept of a tangle, which determines the order of wires on different horizontal layers. The orders can only differ through swaps of neighboring wires. Our main focus is on two related problems: List-Feasibility and Tangle-Height Minimization.
List-Feasibility seeks to find a tangle that realizes a given list of swaps, while Tangle-Height Minimization looks to minimize the number of layers used by the tangle. These problems have been proven to be NP-hard, making them highly challenging to solve.
However, our research takes a step further by showing that List-Feasibility remains NP-hard even when each pair of wires swaps only a constant number of times. On a positive note, we present an algorithm for Tangle-Height Minimization that calculates an optimal tangle for $n$ wires and a given list of swaps in efficient time.
By leveraging this algorithm, we are able to derive a simplified and faster version to solve List-Feasibility. In addition, we demonstrate that List-Feasibility is in NP and fixed-parameter tractable with respect to the number of wires.
We also tackle a specific type of list called “simple” lists, where each swap occurs at most once. For such lists, we showcase an algorithm that solves Tangle-Height Minimization in faster time.
Abstract: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.