Link Crossing Number is NP-hard

Arnaud de Mesmay; Eric Sedgwick; Marcus Schaefer

REVIEW 1 major objections 6 minor 10 references

Link Crossing Number is NP-hard

T0 review · 1 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Testing whether a link diagram represents a link equivalent to one drawn with at most $k$ crossings is NP-hard.

desk verdict First NP-hardness proof for link crossing number, a genuinely important result, but the arXiv version has two repairable proof gaps in the reverse direction; it deserves peer review with mandatory fixes. read the letter →

arxiv 1908.04073 v1 pith:IES3F3RQ submitted 2019-08-12 cs.CG math.GT

Arnaud de Mesmay , Marcus Schaefer , Eric Sedgwick This is my paper · ORCID

classification cs.CGmath.GT MSC 57K1068Q1705C10

keywords linkcrossingnumberNP-hardnesscomputationaltopologyknottheorybipartitelinkingweightedlinksdiagrams

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that the link crossing number problem is NP-hard: given a link diagram and an integer $k$, deciding whether the represented link is equivalent to one drawn with at most $k$ crossings is computationally intractable unless P = NP. The proof reduces the NP-complete bipartite crossing number problem to link crossing number by encoding a bipartite graph as a weighted link built from chains of unknots, hinges, guards, and edge-links. The same gadget shows NP-completeness for the crossing number problem under linking-number and parity-linking-number equivalence, and NP-hardness under link homotopy and concordance. For the authors, this is the first formal computational hardness result for a fundamental knot-theoretic minimization problem.

What carries the argument

The load-bearing gadget is the framework $L(k,\ell)$: a stack of chains of four unknots, where consecutive chains are bound by four linking unknots called hinges. Lemma 2.6 shows that a crossing-minimal drawing of a framework must be the concentric nested layout of Figure 3, with each chain drawn in the outer face of the next; this rigidity is what lets the reduction translate crossings in a link diagram into the ordering of vertices in a bipartite drawing. The second mechanism is the weighting scheme: each component carries an integer weight, crossings count with the product of weights, and Lemma 2.2 guarantees that connected smoothings, which remove self-crossings, do not change linking numbers modulo 2. Together the weights make the intended crossing count of every gadget unavoidable while keeping the accounting linear in the original graph's crossing number $c$. The final removal of weights via parallel copies relies on the constructed components being unknots drawn without self-crossings.

What would settle it

Exhibit, for a small framework $L(2,\ell)$, a diagram with the same pairwise linking parities and with at most $c(L(2,\ell)) + t$ crossings for some small $t$, whose layout is not the concentric nested layout of Figure 3. Such an example would refute the parity-robust rigidity claim on which the proof's reverse direction depends.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: testing whether a link diagram represents a link equivalent to some diagram with at most $k$ crossings is NP-hard. The authors reduce from bipartite crossing number for graphs whose $U$-vertices have degree 4, whose $V$-vertices have degree 1, and with the $V$-order fixed. Given such a graph $G$, they construct a weighted link $L_w$ whose components are unknots arranged as a framework of four-component chains joined by hinges, plus guard unknots and edge-links that copy the incidences of $G$; a bipartite drawing with $c$ crossings yields a diagram of $L_w$ with $c' = c_f + c_g + 8n_U^2 w_1 + 4n_V w_2 + 4c$ weighted crossings, and weights are then removed by replacing each component with parallel copies. For the reverse direction, they use Lemma 2.2, which says connected smoothing preserves linking parity, to reduce any parity-linking-number-equivalent diagram with at most $c'$ crossings to a weighted drawing with the same parity data, then apply Lemma 2.6 to force the framework into its nested layout and read off a bipartite drawing of $G$ with at most $c$ crossings. This is what makes the link crossing number problem NP-hard.

Load-bearing premise

The reverse direction applies Lemma 2.6, which is proved only for crossing-minimal diagrams of the actual framework, to a drawing that is merely parity-linking-number equivalent; if such a drawing can avoid the nested layout while staying near the crossing-number budget, the reduction's conclusion does not follow.

Editorial extensions

If this is right

Unless P = NP, no polynomial-time algorithm can decide whether a link diagram can be redrawn with at most $k$ crossings.
The hardness persists for natural weaker equivalence relations: link homotopy and concordance; for linking-number and parity-linking-number equivalence the decision problem is NP-complete.
Because the proof only needs the parity of linking numbers, any algorithm based on invariants at least as fine as linking parity still faces NP-hardness.
For any fixed $k$, the problem lies in NP, so the hardness is driven by $k$ being part of the input rather than by any fixed crossing budget.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If Lemma 2.6 could be strengthened to hold for any parity-linking-number-equivalent diagram, the same reduction would likely settle the crossing number problem under linkedness-equivalence, which the paper leaves open.
The weighted-framework construction is flexible enough to encode other ordering-constrained optimization problems on bipartite graphs; replacing the edge-links could give hardness for variants such as one-sided crossing minimization with prescribed component groupings.
The paper's concluding question about reducing the number of components suggests a testable route: if the chain-and-hinge framework could be compressed into a single alternating knot, the proof strategy would move toward the still-open knot crossing number problem.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper proves that determining the crossing number of a link is NP-hard, resolving a question that has been open for decades. The reduction is from bipartite crossing number, using weighted links with u-guards, v-guards, and edge-links to encode the graph. The same construction gives NP-completeness for the weaker notions of parity-linking-number and linking-number equivalence. That is genuinely new and significant. The high-level architecture is sound, the forward direction is clean, and the framework gadgets are carefully designed. The paper is clearly written and the authors honestly flag what they do not prove, such as the single-component knot crossing number case.

The soft spots are real but repairable. First, in the reverse direction, the authors select one representative per weighted component and claim the weighted crossing number of the resulting drawing D' is at most c' because the unweighted count did not increase. That is not justified as stated; the representative with fewest total crossings need not have few crossings with each particular other representative. A standard averaging argument would fix it, but it is missing. Second, and more substantive, after bounding the crossings among the weight-w1 components, they invoke Lemma 2.6 to conclude the framework is drawn as in Figure 3. But Lemma 2.6 is stated for a crossing-minimal drawing of the actual framework link, while D' is only parity-linking-number equivalent to Lw. The budget rules out extra crossings, but it does not by itself force the nested layout. You need a stronger parity-robust rigidity statement: any diagram with the same pairwise linking parities and the same crossing count must have the framework layout. That statement is likely true, but it is not proved here, and re-deriving Lemma 2.6 under those weaker hypotheses requires nontrivial work. Third, there is a minor indexing typo: the hinge range in the framework definition should be 0 ≤ i < k, not 1 ≤ i < k, to match the crossing count and the proof.

None of this makes me doubt the result. The approach is credible, and the published version probably fixes these gaps. But the arXiv v1 is not fully self-contained. This is the paper to cite for "link crossing number is hard." It deserves a serious referee, not a desk reject, but the referee should insist on the missing rigidity lemma and the averaging argument before acceptance.

Referee Report

1 major / 6 minor

Summary. This paper claims the first NP-hardness result for the link crossing number problem. The proof reduces from the NP-complete one-sided bipartite crossing number problem (Theorem 2.1, due to Muñoz–Unger–Vrťo) for graphs whose U-vertices all have degree 4 and whose V-order is fixed. The reduction builds a weighted link Lw whose components are unknots organized as a 'framework' of chains (rings) and hinges, augmented by U-guards, V-guards, and edge-link unknots encoding the edges of G; weights w1 > w2 > 1 are chosen as large polynomials so that a threshold c′ separates intended from unintended crossings via inequalities (i)–(iv). Lemma 2.4 replaces each weighted component by several parallel copies, yielding an unweighted link L′ whose isotopy class does not depend on the drawing, and the main theorem asserts c(L′) ≤ c′ if and only if bcr(G) ≤ c. The same framework is claimed to give NP-completeness for the crossing-number problems under parity-linking-number and linking-number equivalence, and NP-hardness under link homotopy and concordance (Corollary 1.2). The paper closes with a discussion of linkedness equivalence, fixed-k crossing numbers, and open questions.

Significance. The main theorem, if its proof is completed, resolves an open problem that has been noted explicitly in the knot theory literature: no formal hardness was previously known for computing the crossing number of a link, in contrast to the situation for graph crossing numbers. The reduction's gadget architecture — weighted unknots, rigid chain-and-hinge frameworks with a uniqueness lemma, guards, and edge-links — is clever and likely to be reusable in further topology hardness arguments, and the cabling trick of Lemma 2.4 for removing weights is elegant. The paper correctly identifies the parity-linking structure as the source of hardness and obtains a clean hierarchy of corollaries for coarser equivalence relations. The forward direction is carefully argued, the source problem is an established NP-complete problem (so there is no circularity), and the paper is honest about its limitations (linkedness equivalence, the single-component case, and the link-equivalence bottleneck for NP-membership). However, two load-bearing steps in the reverse direction are not justified as written, and until they are repaired the theorem should be regarded as conditional.

major comments (1)

[Section 3, reverse direction (statement 'Lemma 2.6 then allows us to conclude that the frame is drawn exactly as…] The diagram D′ is only parity-linking-number equivalent to the weighted link Lw; it is not a diagram of the framework L(k,ℓ). Lemma 2.6 is stated and proved only for crossing-minimal diagrams of L(k,ℓ) itself, and its proof uses facts specific to that isotopy class: that the chain and hinge components are actually linked so their crossings are unavoidable, the face structure from Lemma 2.5(iii)–(iv), and the K2,4 planarity argument for the relative nesting of chains. None of these layout conclusions is re-derived for a diagram that merely has the same pairwise linking parities as the framework. The budget argument shows that two weight-w1 components cross either twice or not at all and that the parity graph matches the framework adjacency graph, but this does not force the nested, hinged layout of Figure 3: alternative non-nested arrangements of the chains, different nesting orders, and different placements of the hinges are not excluded. The proof needs a new parity-robust rigidity statement — any diagram whose pairwise parity-linking matrix agrees with that of the framework and whose w1-subdiagram has exactly the framework minimum number of crossings must have the layout of Figure 3 — and this is not a corollary of the stated Lemma 2.6. This gap is load-bearing because it is the only mechanism converting a hypothesized drawing of an arbitrary parity-equivalent link back into a bipartite drawing of G; the invocation also inherits the weighted-count problem of the next comment.

minor comments (6)

[Lemma 2.6 and Section 3 (value of cframe)] The stated value c(D) = 24k+2ℓ appears inconsistent with the framework definition: hinges are added only for 1 ≤ i < k, so there are 4(k−1) hinges, and each hinge must cross each of its two rings at least twice, giving 8k+2ℓ+16(k−1) = 24k+2ℓ−16 rather than 24k+2ℓ. Accordingly the value cframe = (56n_U+8)w1² in Section 3 appears to be 16w1² too large, and the parity graph of the framework contains 28n_U−4 odd pairs, so the lower bound in the reverse direction should be (56n_U−8)w1². The reduction is asymptotically unaffected, but the constants should be re-derived; the displayed formula for cframe also contains a bracket typo.
[Section 3, choice of weights] Taking w1 = 12n_U²w2 + 80n_U² gives only a non-strict inequality in the estimate used to justify condition (i), since the right-hand side is bounded above by exactly w1(12n_U²w2+80n_U²) = w1². Choose w1 strictly larger, for example w1 = 12n_U²w2+80n_U²+1.
[Section 3, final paragraph ('Picking, for each edge, the arc with fewer crossings')] The step concluding 'a bipartite drawing of G with at most 4c/4 = c crossings' needs a written counting argument. From a total of 4c crossings among edge-links, choosing for each edge one of its two arcs does not automatically divide the crossing count by four; one must show (as is presumably visible in Figure 5) that the four crossings between two edge-links are distributed one per pair of arcs, so that the chosen arcs cross at most once per crossing pair of edges.
[General notation in Section 3] The symbol c is used for the crossing number of a diagram c(D), the crossing number of a link c(L), the number of crossings in the bipartite drawing of G, and the residual edge-link crossing budget in the reverse direction; similarly k denotes both the input threshold and the number of chains in the framework. This makes Section 3 hard to follow; please use distinct symbols for these quantities.
[Lemmas 2.5 and 2.6] The phrase 'up to a homeomorphism of the surface' is ambiguous between the plane and the sphere, and the claim that each chain bounds an inner and an outer face suggests the sphere is intended; please state the convention explicitly.
[Figures 3 and 5] Several of the crossing counts involving edge-links (8n_U²w1, 4n_Vw2, 4c) and the layout claims for the framework and guards are justified only by reference to Figures 3 and 5, but the figure content could not be verified from the text supplied to me. The authors should make these counts checkable from the text or ensure that the figures are legible and clearly labeled.

Circularity Check

0 steps flagged · score 1.0 of 10

No circularity; the reduction is anchored in an external NP-complete problem and internal lemmas, with only a non-load-bearing self-cited survey.

full rationale

Walking the derivation chain: the paper proves Theorem 1.1 by a polynomial reduction from the bipartite crossing number problem restricted to bipartite graphs with all U-vertices of degree 4, all V-vertices of degree 1, and a fixed order of V-vertices. This starting problem is Theorem 2.1, attributed to Muñoz, Unger, and Vrto (reference [7]), an external NP-completeness result. The construction maps an input graph G to a weighted link L_w using a framework of chains and hinges, U-guards, V-guards, and edge-links. The weights w1 and w2 are chosen at the end solely to satisfy the four budget inequalities (i)-(iv), using bounds involving nU, nV, and c; they are not fitted to any target crossing-number value or to the output of the hardness claim. The forward direction explicitly converts a bipartite drawing with at most c crossings into a weighted link diagram with at most c' crossings. The reverse direction starts from any parity-linking-number-equivalent diagram with at most c' crossings, removes self-crossings via Lemma 2.2 and the component-selection procedure, then uses the budget inequalities to force the intended framework layout and extract a bipartite drawing with at most c crossings. The rigidity statements used here, Lemmas 2.5 and 2.6, are proved inside the paper by counting unavoidable crossings and using the parity of linking numbers; they are not imported from the authors' prior hardness results, and they are not defined in terms of the target conclusion. The only self-citation is reference [8], a survey of graph crossing number variants, used as background context for known restrictions of the bipartite crossing number problem; the load-bearing NP-completeness premise is cited to [7], not to the authors' own work. The reader-identified weakness about applying Lemma 2.6 to a diagram that is only parity-linking-number equivalent, rather than a crossing-minimal diagram of the actual framework link, is a potential correctness gap in the reverse direction, but it is not circularity: the conclusion is not an input to the construction, and the missing argument is not a self-citation or a fitted parameter renamed as a prediction. Therefore no significant circularity is present.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central claim rests on an external NP-completeness result and on topological rigidity of certain link diagrams. The weights w1 and w2 are chosen by hand to enforce strict inequalities; they are not fitted to data, and the exact values are not load-bearing. No new physical or mathematical entities are introduced.

free parameters (2)

w2 = 80 n_U^2 or any sufficiently large polynomial
Weight assigned to guard components; chosen to satisfy inequality (ii) in Section 3. The text's constant 80 has a small arithmetic slack against the derived bound 88, but the choice is asymptotic and repairable.
w1 = 12 n_U^2 w2 + 80 n_U^2
Weight assigned to framework components; chosen to satisfy inequalities (i), (iii), and (iv). The central reduction depends on the existence of such weights, not their exact values.

assumptions (3)

domain assumption Bipartite crossing number is NP-complete for the restricted class in Theorem 2.1, where all U vertices have degree 4, all V vertices have degree 1, and the order of V is fixed.
This is the external NP-complete problem used as the reduction source; the paper cites Munoz, Unger, and Vrto [7] and relies on it without proof.
standard math Two components with odd linking number parity must cross at least twice in any diagram.
Used throughout the reverse direction in Section 3 to lower-bound crossings between framework components, guards, and edge-links.
ad hoc to paper The framework rigidity Lemma 2.6 applies not only to crossing-minimal diagrams of the framework link but also to any parity-linking-number-equivalent drawing with at most the budgeted crossings.
The reverse direction in Section 3 applies Lemma 2.6 to a drawing D' that is only parity-linking-number equivalent to the weighted link, not isotopic; the lemma as stated and proved covers crossing-minimal diagrams of the actual framework. This generalization is not proven.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Link Crossing Number is NP-hard." pith.science (2026). https://pith.science/paper/IES3F3RQ

@misc{pith2026190804073,
  author       = {Pith},
  title        = {Pith review of: Link Crossing Number is NP-hard},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IES3F3RQ}},
  note         = {Machine review of arXiv:1908.04073}
}

read the original 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.

Figures

Figures reproduced from arXiv: 1908.04073 by the authors.

**Figure 2.** An n-chain, for n = 4. (iii) the two crossings a component has with another component are consecutive; that is, along each component, the four crossings with its two neighboring components do not interleave, and (iv) there are two faces of D each bounded by n arcs, one arc from each component of L, occurring in the reverse order as they do along the chain. We call these the inner and outer face of L. In other words… view at source ↗

**Figure 3.** A framework, for k = 3 and ` = 6. Lemma 2.6. Let D be a crossing-minimal drawing of a framework L(k, `), with k ≥ 0, and ` ≥ 4. Then c(D) = c(L) = 24k + 2`. Moreover, up to a homeomorphism of the surface we can assume that (i) chain Li is drawn in the outer face of Li+1, for 0 ≤ i < k, (ii) we can draw an (open, simple) curve γ that crosses L0, . . . , Lk in that order, crossing each Li exactly twice; γ can be made … view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: A sample bipartite graph in which all vertices of [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

**Figure 5.** Figure 5: Link diagram of L w for the sample graph G from [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

An upper bound on Reidemeis- ter moves

Alexander Coward and Marc Lackenby. An upper bound on Reidemeis- ter moves. Amer. J. Math. , 136(4):1023–1066, 2014

work page 2014
[2]

Fox and John W

Ralph H. Fox and John W. Milnor. Singularities of 2-spheres in 4-space and cobordism of knots. Osaka Math. J. , 3:257–267, 1966

work page 1966
[3]

Lagarias, and Nicholas Pippenger

Joel Hass, Jeﬀrey C. Lagarias, and Nicholas Pippenger. The computa- tional complexity of knot and link problems. J. ACM, 46(2):185–211, 1999. 15

work page 1999
[4]

The efficient certification of knottedness and Thurston norm

Marc Lackenby. The eﬃcient certiﬁcation of knottedness and thurston norm. arXiv preprint arXiv:1604.00290 , 2016

work page Pith review arXiv 2016
[5]

Elementary knot theory

Marc Lackenby. Elementary knot theory. In Lectures on geometry, Clay Lect. Notes, pages 29–64. Oxford Univ. Press, Oxford, 2017

work page 2017
[6]

Link groups

John Milnor. Link groups. Ann. of Math , 59(2):177–195, 1954

work page 1954
[7]

One sided crossing minimization is NP-hard for sparse graphs

Xavier Mu˜ noz, Walter Unger, and Imrich Vr ˇto. One sided crossing minimization is NP-hard for sparse graphs. In Graph drawing (Vienna, 2001), volume 2265 of Lecture Notes in Comput. Sci. , pages 115–123. Springer, Berlin, 2002

work page 2001
[8]

The graph crossing number and its variants: A survey

Marcus Schaefer. The graph crossing number and its variants: A survey. The Electronic Journal of Combinatorics , 2013. Dynamic Survey 21 (last updated December 22nd, 2017

work page 2013

Show all 10 references

[9]

A low and a high hierarchy within NP

Uwe Sch¨ oning. A low and a high hierarchy within NP. J. Comput. System Sci., 27(1):14–28, 1983

1983
[10]

P. G. Tait. On knots. Proc. R. Soc. Edinburgh, 9:306–317, 1877. 16 Figure 5: Link diagram of Lw for the sample graph G from Figure 4. Some underedges under two adjacent subarcs of the edge links have been omitted for clarity. 17

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

An upper bound on Reidemeis- ter moves

Alexander Coward and Marc Lackenby. An upper bound on Reidemeis- ter moves. Amer. J. Math. , 136(4):1023–1066, 2014

work page 2014

[2] [2]

Fox and John W

Ralph H. Fox and John W. Milnor. Singularities of 2-spheres in 4-space and cobordism of knots. Osaka Math. J. , 3:257–267, 1966

work page 1966

[3] [3]

Lagarias, and Nicholas Pippenger

Joel Hass, Jeﬀrey C. Lagarias, and Nicholas Pippenger. The computa- tional complexity of knot and link problems. J. ACM, 46(2):185–211, 1999. 15

work page 1999

[4] [4]

The efficient certification of knottedness and Thurston norm

Marc Lackenby. The eﬃcient certiﬁcation of knottedness and thurston norm. arXiv preprint arXiv:1604.00290 , 2016

work page Pith review arXiv 2016

[5] [5]

Elementary knot theory

Marc Lackenby. Elementary knot theory. In Lectures on geometry, Clay Lect. Notes, pages 29–64. Oxford Univ. Press, Oxford, 2017

work page 2017

[6] [6]

Link groups

John Milnor. Link groups. Ann. of Math , 59(2):177–195, 1954

work page 1954

[7] [7]

One sided crossing minimization is NP-hard for sparse graphs

Xavier Mu˜ noz, Walter Unger, and Imrich Vr ˇto. One sided crossing minimization is NP-hard for sparse graphs. In Graph drawing (Vienna, 2001), volume 2265 of Lecture Notes in Comput. Sci. , pages 115–123. Springer, Berlin, 2002

work page 2001

[8] [8]

The graph crossing number and its variants: A survey

Marcus Schaefer. The graph crossing number and its variants: A survey. The Electronic Journal of Combinatorics , 2013. Dynamic Survey 21 (last updated December 22nd, 2017

work page 2013