The complexity of finding tangles

DOI10.1007/978-3-031-23101-8_1MaRDI QIDQ6114453zbMATH OpenOpenAlexFDO

Authors Oksana Firman, Philipp Kindermann, Boris Klemz, Oleksandr Ravs'kyj, Alexander Wolff, Johannes Zink

Publication date 14 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.12251

zbMATH Keywords

exponential-time algorithmFPTNP-hardnesstangle

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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.

Recommendations

• Computing height-optimal tangles faster
• Computing with tangles
• Drawing permutations with few corners
• Computing with Tangles
• Drawing (Complete) Binary Tanglegrams

Cites work

• A function for evaluating the computing time of a bubbling system
• Classification of strange attractors by integers
• Computing height-optimal tangles faster
• Drawing permutations with few corners
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 1940733 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Knotted periodic orbits in dynamical systems. I: Lorenz's equations
• Representing permutations with few moves
• The complexity of satisfiability problems
• Visualizing the template of a chaotic attractor

Cited in

(5)

• Computing height-optimal tangles faster
• The prevalence of persistent tangles
• Tangles are Decided by Weighted Vertex Sets
• Computing with Tangles
• Minimizing the height of simple tangles

This page was built for publication: The complexity of finding tangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6114453)