Link crossing number is NP-hard

DOI10.1142/S0218216520500431MaRDI QIDQ5118878zbMATHOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

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)