Link crossing number is NP-hard
DOI10.1142/S0218216520500431zbMath1455.57010arXiv1908.04073OpenAlexW3026370620MaRDI QIDQ5118878
Eric Sedgwick, Marcus Schaefer, Arnaud de Mesmay
Publication date: 27 August 2020
Published in: Journal of Knot Theory and Its Ramifications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1908.04073
computational complexityknotlinkNP-hardNP-completelinking numbercrossing number of graphscrossing number of links
Graph theory (including graph drawing) in computer science (68R10) Relations of low-dimensional topology with graph theory (57M15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Knot theory (57K10)
Cites Work
- Unnamed Item
- A low and a high hierarchy within NP
- The graph crossing number and its variants: a survey
- Some conditionally hard problems on links and 3-manifolds
- Singularities of 2-spheres in 4-space and cobordism of knots
- Link groups
- An upper bound on Reidemeister moves
- The computational complexity of knot and link problems
- Elementary knot theory
This page was built for publication: Link crossing number is NP-hard