Link crossing number is NP-hard

DOI10.1142/S0218216520500431zbMATH Open1455.57010arXiv1908.04073OpenAlexW3026370620MaRDI QIDQ5118878FDOQ5118878

Authors: Arnaud de Mesmay, Marcus Schaefer, Eric Sedgwick 

Publication date: 27 August 2020

Published in: Journal of Knot Theory and Its Ramifications (Search for Journal in Brave)

Abstract: We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.

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

Recommendations

• NP-hard problems naturally arising in knot theory
• Crossing number is hard for cubic graphs
• Mathematical Foundations of Computer Science 2004
• Which crossing number is it anyway?
• The unbearable hardness of unknotting

zbMATH Keywords

computational complexityNP-completeNP-hardknotlinklinking numbercrossing number of graphscrossing number of links

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Relations of low-dimensional topology with graph theory (57M15) Knot theory (57K10)

Cites Work

• The graph crossing number and its variants: a survey
• Title not available (Why is that?)
• Link groups
• The computational complexity of knot and link problems
• A low and a high hierarchy within NP
• Singularities of 2-spheres in 4-space and cobordism of knots
• Elementary knot theory
• An upper bound on Reidemeister moves
• Some conditionally hard problems on links and 3-manifolds

This page was built for publication: Link crossing number is NP-hard

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