Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2002.12251 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913181217062912 |
|---|---|
| author | Firman, Oksana Kindermann, Philipp Klemz, Boris Ravsky, Alexander Wolff, Alexander Zink, Johannes |
| author_facet | Firman, Oksana Kindermann, Philipp Klemz, Boris Ravsky, Alexander Wolff, Alexander Zink, Johannes |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2002_12251 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | The Complexity of Finding Tangles Firman, Oksana Kindermann, Philipp Klemz, Boris Ravsky, Alexander Wolff, Alexander Zink, Johannes Discrete Mathematics 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. |
| title | The Complexity of Finding Tangles |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2002.12251 |