Link Crossing Number is NP-hard

2019/08/12 by de Mesmay, Arnaud, Schaefer, Marcus, Sedgwick, Eric
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT)

paper · doi:10.48550/arxiv.1908.04073

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.

Related

• Links with splitting number one
• Crossing Number is NP-hard for Constant Path-width (and Tree-width)
• A Simple Characterization of Adequate Links
• Hardness of approximation for crossing number
• When can a link be obtained from another using crossing exchanges and\n smoothings?