论文标题
寻找缠结的复杂性
The Complexity of Finding Tangles
论文作者
论文摘要
我们研究以下组合问题。给定一组$ n $ y子酮曲线，我们称之为电线，缠结确定了许多水平层上电线的顺序，因此任何两个连续的层仅在相邻电线的掉期交换方面有所不同。给定一个多层$ l $互换（即无线对电线）和电线的初始顺序，如果每对电线更改其订单的订单，则意识到$ L $，如$ L $所指定的次数多次。确定给定的多组掉期是否承认意识到纠缠是NP-hard [Yamanaka等，CCCG 2018]。我们证明，如果每对电线仅交换恒定次数，那么这个问题仍然是NP-HARD。从积极的一面来看，我们提高了以前的指数时间算法的运行时间。我们还表明，相对于电线数量，该问题是在NP中进行的，并且可以进行固定参数。
We study the following combinatorial problem. Given a set of $n$ y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers such that 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$. Deciding whether a given multiset of swaps admits a realizing tangle is known to be NP-hard [Yamanaka et al., CCCG 2018]. We prove that this problem remains NP-hard if every pair of wires swaps only a constant number of times. On the positive side, we improve the runtime of a previous exponential-time algorithm. We also show that the problem is in NP and fixed-parameter tractable with respect to the number of wires.
