REVIEW 2 major objections 5 minor 11 references
NP-Hardness of Non-Crossing Hamiltonian Path and Cycle in Non-Planar Graphs
T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A direct 3-SAT reduction shows non-crossing Hamiltonian path and cycle are NP-complete in non-planar embedded graphs.
desk verdict Novel direct reduction, but the non-crossing claim is unproven; deserves serious refereeing to settle the geometry. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the variable ring: each of n concentric rings with 3(m+1) vertices encodes one variable, with clockwise traversal meaning true and counterclockwise meaning false. Clause gadgets are chains of n+1 vertices placed inside the innermost ring, with bidirectional edges connecting ring positions v(i,3j-1) and v(i,3j) to clause vertex c(i,j), and a directed edge from a literal vertex to c(0,j) whenever that literal occurs in clause c_j. The path argument rests on detours that leave a ring at v(i,3j-1), collect a prefix of the clause column, rejoin at v(i,3j), and never jump between rings through clause vertices; Theorem 2 proves that any cross-ring clause detour would force a ring vertex to become an endpoint. For the cycle version, dummy ring pairs between consecutive real rings and dummy clause vertices provide a return pass from t to s, with four traversal options selected by a table based on the forward-pass entry and exit points.
What would settle it
For a fixed small formula, enumerate all placements of the rings and clause gadgets that satisfy the paper's bulleted constraints and check whether any detour described in Theorem 1 or Theorem 3 crosses an existing edge; if every placement has such a crossing, the central theorem would fail.
Extended reading notes
Core claim
The paper's central claim is that the non-crossing Hamiltonian path problem (NCHP) and the non-crossing Hamiltonian cycle problem (NCHC) are NP-complete, and that this can be established by a direct reduction from 3-SAT that never forces the underlying graph to be planar. For every formula phi, the reduction constructs an embedded graph G_phi such that a non-crossing Hamiltonian path exists if and only if $\varphi$ is satisfiable, and an augmented graph G_phi^cycle such that a non-crossing Hamiltonian cycle exists if and only if $\varphi$ is satisfiable. The two theorems that build paths and cycles from satisfying assignments, and the two that recover satisfying assignments from non-crossing paths and cycles, together give the equivalence. The intended upshot is that the difficulty lives in the geometric restriction on the path, not in the planarity of the graph.
Load-bearing premise
The reduction assumes the ring and clause gadgets can actually be drawn in the plane so that every detour described in the proofs is non-crossing, but the paper gives placement rules and figures rather than a coordinate-based proof.
Editorial extensions
If this is right
- If the reduction is sound, both NCHP and NCHC remain NP-complete even when the underlying embedding is far from planar, so the hardness is intrinsic to the non-crossing constraint.
- The reduction uses a sparse graph and avoids crossover gadgets, giving a more transparent route for proving NP-hardness of other non-crossing path and cycle variants.
- Membership in NP follows because a candidate path or cycle can be verified in polynomial time, so the problems are NP-complete rather than merely NP-hard.
- The construction has polynomial size in the number of variables and clauses, so the reduction is a valid polynomial-time many-one reduction.
- The cycle version inherits the path hardness by adding dummy rings that supply a return path, so cycle hardness is not obtained simply by reusing the path result unmodified.
Reading between the lines
- Inference: the paper does not give a coordinate-based proof that all claimed detours are non-crossing; an explicit embedding lemma would turn the qualitative placement rules into a fully formal reduction.
- Inference: the same ring-and-detour scheme may adapt to bichromatic point sets or alternating non-crossing path problems, where the non-crossing constraint also appears to be the source of hardness.
- Inference: testing small formulas, such as two variables and two clauses, by exhaustive search over drawings that respect the placement bullets could reveal whether any hidden crossing exists in the claimed detours.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a direct polynomial-time reduction from 3-SAT to the non-crossing Hamiltonian path (NCHP) and non-crossing Hamiltonian cycle (NCHC) problems on arbitrary embedded graphs, avoiding planar crossover gadgets. It constructs, for a formula φ, a graph G_φ with concentric variable rings and directed clause chains, and claims that φ is satisfiable iff G_φ has a non-crossing Hamiltonian path (Theorems 1 and 2). It then extends the construction to a cycle graph G_φ^cycle by adding dummy ring pairs and dummy clause vertices, claiming an analogous iff result (Theorems 3 and 4). The reverse directions use a degree-counting argument whose goal is to show that clause detours cannot jump between rings. The paper concludes that NCHP and NCHC are NP-complete.
Significance. If the missing geometric verification were supplied, the reduction would be a useful conceptual contribution: it avoids crossover and planarity-forcing gadgets and gives a transparent way to see how the non-crossing constraint alone can create hardness. The construction is polynomial-size, the forward detour rule is explicit, and the reverse direction attempts a structural statement that does not rely on the non-crossing assumption. However, in the current manuscript the central if-direction is not proven: the existence of a plane embedding in which all detours are pairwise non-crossing is asserted from placement bullets and figures rather than demonstrated. The cycle extension and the claimed non-planarity of the constructed graphs are also under-proved. With those gaps filled, the paper would meet the bar for a solid conference result; as it stands, the main theorem is not verifiable from the written proof.
major comments (2)
- [§2.1, Theorem 1] The existence of a plane embedding realizing the placement bullets is asserted but not proved, and the non-crossing claim for the constructed Hamiltonian path is not established. The proof only says that a detour is 'directed inward' and therefore avoids crossings with prior path edges; it does not rule out crossings between a detour edge used from an outer satisfying ring to c(0,j) and the later Case-2 edges v(k,3j-1)-c(k,j) or c(k,j)-v(k,3j) for k > i. In the bullet layout, the clause column lies between the v(.,3j-1) and v(.,3j) columns, and the two segments have alternating endpoints around the ring, so a straight-line realization would cross; a non-straight-line routing is never specified or proven crossing-free. The iff claim therefore lacks its central geometric half. Please give explicit coordinates or a topological curve specification for all edges and verify pairwise non-crossing of the complete detour set.
- [§3.2, §3.3 (Theorem 4)] Theorem 4 does not actually reduce to Theorem 2 as written. The insertion of e(i,j) and e'(i,j) changes the neighborhood of each c(i,j), so the degree-counting argument in Theorem 2 does not apply verbatim; for example, c(r1,j) now has an incoming edge from e'(r1-1,j) and an outgoing edge to e(r1,j), rather than the original chain neighbors. The sentence 'the same argument as in Theorem 2 shows...' needs a separate argument or a precise reduction that handles the dummy clause vertices. Likewise, the four dummy-pair traversal options in Section 3.2 (Table 1, Figure 6) assert non-crossing of the return pass without a geometric proof; the zig-zag option in particular introduces new detour edges d(i,3j-1)-e(i,j), e(i,j)-e'(i,j), and e'(i,j)-d'(i,3j) whose crossing behavior with other zig-zag hops is unchecked. Since the cycle result depends on these assertions, this is load-bearing.
minor comments (5)
- [§2.1] The claim that G_φ is non-planar via a K3,3 minor is relegated to 'leave the details as an exercise.' This matters for the paper's framing that the reduction does not rely on planarity; please provide the explicit minor or a precise reference.
- [§2.2, Figure 4] In the left panel of Figure 4, only c1 and c2 are labeled explicitly; the remaining clause labels are not readable. Please enlarge the figure or list all clauses in the caption.
- [§2.3, Theorem 2] The proof of Theorem 2 never uses the non-crossing assumption. If that is intended, the paper should state it explicitly; if not, the role of non-crossing in the converse direction should be clarified.
- [§3.1, Convention 2] Convention 2 relies on purple color, which will not be visible in a monochrome print version. Please restate the convention using line style or grey levels as well.
- [§2.1] The sentence 'Assume φ contains an even number of clauses by duplicating a clause if necessary' should state explicitly that duplicating a clause preserves satisfiability and that m is then even; this is clear but should be said.
Circularity Check
No circular dependency: the reduction is anchored to external 3-SAT and introduces no fitted parameters or load-bearing self-citations.
full rationale
The derivation chain is a standard many-one reduction from 3-SAT to NCHP/NCHC. The graphs G_phi and G_cycle_phi are constructed directly from the formula phi in Sections 2.1 and 3.1, the forward directions (Theorems 1 and 3) explicitly build a non-crossing Hamiltonian path or cycle from a satisfying assignment, and the converse directions (Theorems 2 and 4) use local degree and endpoint arguments. No equation is defined in terms of the target problem, no parameter is fitted to data, and no prediction is equivalent to an input by construction. The only self-citation is reference [11], included in a general introductory list of prior work on non-crossing structures; it is not used to justify the reduction, to supply a uniqueness theorem, or to restrict alternatives. The absence of a fully formal embedding proof for the detour edges is a correctness or rigor gap, not a circularity, because the needed assertion is about the existence of a geometric realization, not about the hardness claim being assumed. The central claim therefore has independent content supplied by the explicit gadget construction and the reduction from 3-SAT.
Assumptions & free parameters
assumptions (3)
- standard math 3-SAT is NP-complete
- ad hoc to paper G_phi admits an embedding realizing the informal placement bullets in Section 2.1 such that all detour paths in Theorems 1 and 3 are non-crossing
- domain assumption For every 3-SAT instance the constructed graph is non-planar
Cite this review
Pith. "Pith review of NP-Hardness of Non-Crossing Hamiltonian Path and Cycle in Non-Planar Graphs." pith.science (2026). https://pith.science/paper/YH3FGYQM
@misc{pith2026260806255,
author = {Pith},
title = {Pith review of: NP-Hardness of Non-Crossing Hamiltonian Path and Cycle in Non-Planar Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/YH3FGYQM}},
note = {Machine review of arXiv:2608.06255}
}
read the original abstract
We seek to disentangle the hardness of finding a Hamiltonian path or cycle from the hardness of finding a non-crossing path or cycle by giving a direct reduction from 3-SAT to the non-crossing Hamiltonian path and cycle problems on non-planar graphs. Prior hardness proofs proceed by reduction to planar graphs, where every path is automatically non-crossing; this conflates the two sources of difficulty and leaves unclear why forbidding crossings on the path alone makes the problem hard. Our reduction places the difficulty squarely in the non-crossing constraint, avoids planar gadget constructions, and yields a more transparent proof that may be easier to extend to related problems.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
M. Abellanas, J. Garc ´ ıa, G. Hern´ andez, M. Noy, and P. Ramos. Bipartite embeddings of trees in the plane.Discrete Applied Mathematics, 93(2):141– 148, 1999
work page 1999
-
[2]
Sayan Bandyapadhyay, Aritra Banik, Sujoy Bhore, and Martin N¨ ollenburg. Geometric planar networks on bichromatic collinear points.Theoretical Com- puter Science, 895, 09 2021
work page 2021
-
[3]
Non-crossing Hamiltonian paths and cycles in output-polynomial time
David Eppstein. Non-crossing Hamiltonian paths and cycles in output-polynomial time. In39th In- ternational Symposium on Computational Geome- try (SoCG 2023), pages 29:1–29:16, 2023. CCCG 2026, Orillia, Canada, August 12–14, 2026
work page 2023
-
[4]
Michael R. Garey and David S. Johnson.Com- puters and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979
work page 1979
-
[5]
Michael R. Garey, David S. Johnson, and Larry Stockmeyer. Some simplified NP-complete prob- lems. InProceedings of the 6th Annual ACM Sym- posium on Theory of Computing (STOC), pages 47–63, 1974
work page 1974
-
[6]
Michael R. Garey, David S. Johnson, and Robert E. Tarjan. The planar Hamiltonian circuit problem is NP-complete.SIAM Journal on Computing, 5(4):704–714, 1976
work page 1976
-
[7]
Kano.Discrete Geometry on Red and Blue Points in the Plane — A Sur- vey —, pages 551–570
Atsushi Kaneko and M. Kano.Discrete Geometry on Red and Blue Points in the Plane — A Sur- vey —, pages 551–570. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003
work page 2003
-
[8]
Long al- ternating paths in bicolored point sets.Discrete Mathematics, 308(19):4315–4321, 2008
Jan Kynˇ cl, J´ anos Pach, and G´ eza T´ oth. Long al- ternating paths in bicolored point sets.Discrete Mathematics, 308(19):4315–4321, 2008. Simonovits ’06
work page 2008
Show all 11 references
-
[9]
The NP-completeness of the Hamil- tonian cycle problem in planar digraphs with de- gree bound two.Information Processing Letters, 8(4):199–201, 1979
J´ an Plesn ´ ık. The NP-completeness of the Hamil- tonian cycle problem in planar digraphs with de- gree bound two.Information Processing Letters, 8(4):199–201, 1979
1979
-
[10]
Bicolored point sets admitting non-crossing alternating Hamiltonian paths, 2024
Jan Soukup. Bicolored point sets admitting non-crossing alternating Hamiltonian paths, 2024. https://arxiv.org/abs/2404.06105
2024 arXiv
-
[11]
Enumeration of non-crossing Hamiltonian paths by reachabil- ity checks and bidirectional search
Randal Tuggle and Jack Snoeyink. Enumeration of non-crossing Hamiltonian paths by reachabil- ity checks and bidirectional search. In32nd An- nual Fall Workshop on Computational Geometry (FWCG 2025), 2025.https://www.cs.qc.cuny. edu/goswami/fwcg-2025.html
2025
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.