{"id":"d7088bae-df4b-4c1f-91b9-5039e7201f19","arxiv_id":"2608.06255","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A direct 3-SAT reduction proves NP-completeness of non-crossing Hamiltonian path and cycle in embedded non-planar graphs, avoiding planar crossover gadgets.","lead":"This paper gives a new reduction from 3-SAT to the problem of finding a Hamiltonian path or cycle that does not cross itself, in graphs that are not necessarily planar. The authors aim to show that forbidding crossings, not planarity, is what makes these problems hard.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Load-bearing gap: no formal proof that the Theorem 1 detour edges are pairwise non-crossing in a single embedding; the Section 2.1 placement admits straight-line crossings and no curve-routing is specified.","rationale":"The reader's weakest assumption is exactly the load-bearing gap I identify: the paper never proves the existence of an embedding in which all detours described in Theorems 1 and 3 are non-crossing. My reading confirms this is not a minor exposition issue. The construction couples detour edges that can mutually cross: a long literal edge to c(0,j) coexists in the same path with later ring-to-clause edges for inner rings. The manuscript's only defense is a geometric intuition about inward detours, which does not address crossings among future detour edges. The cycle construction is even more under-specified, since the return pass adds a second set of edges whose mutual non-crossing and non-crossing with the forward pass are asserted by figure and table rather than proved. I therefore do not think the proof as written establishes the central claim; however, the combinatorial skeleton (Theorem 2) is plausible and the gap is addressable by supplying a concrete embedding or a formal routing argument. Thus the appropriate verdict remains CONDITIONAL, matching the reader's assessment. No additional objection, such as the non-planarity proof being left as an exercise, changes this verdict, since non-planarity is not load-bearing for the reduction's correctness.","tokens_in":7918,"tokens_out":34548,"duration_ms":343930,"concrete_test":"Take the smallest nontrivial case from Section 2.1: n=3, m=1, formula phi=(x1 or x2 or x3), satisfying assignment all true. Instantiate the concentric rings, place the c(0..3,1) column between the v(i,2) and v(i,3) columns exactly as the bullets describe, and draw the Theorem 1 Hamiltonian path. Test all pairs of path edges for intersections, specifically whether v(1,2) -> c(0,1) crosses v(2,2) -> c(2,1) or c(2,1) -> v(2,3), and similarly for ring 3. If any pair crosses, either supply explicit coordinates or a curve-routing that avoids the crossing, or the described construction fails. This check directly tests the missing geometric lemma that the proof needs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The forward direction of the reduction (Theorem 1, and its cycle analogue Theorem 3) requires that, for every satisfying assignment, the constructed Hamiltonian path is non-crossing in the fixed embedding of G_phi. The paper supports this only with qualitative placement bullets (Section 2.1) and figures; no coordinates or topological crossing-avoidance argument are given. The issue is concrete: when clause c_j is first satisfied at ring i, the path uses the literal edge v(i,3j-1) -> c(0,j) (or its mirror). Later, for each ring k > i, Case 2 of Theorem 1 uses v(k,3j-1) -> c(k,j) and c(k,j) -> v(k,3j). In the stated layout the c-column lies between the v(.,3j-1) and v(.,3j) columns, with c(0,j) at the inner end. Under the natural straight-line reading, the segment from an outer ring to c(0,j) and the horizontal segment from a lower row to c(k,j) cross by an alternating-endpoint argument. The proof's assertion that the detour is 'directed inward' only addresses crossings with earlier path edges, not with later detour edges. The cycle return pass faces the same unproven geometry with dummy-ring transitions. If such crossings occur on a canonical path, the claimed non-crossing Hamiltonian path need not exist, so the reduction's central if-direction is unproved.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8190,"tokens_out":8563,"duration_ms":80386,"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":[{"comment":"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.","section":"§2.1, Theorem 1"},{"comment":"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.","section":"§3.2, §3.3 (Theorem 4)"}],"minor_comments":[{"comment":"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.","section":"§2.1"},{"comment":"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.","section":"§2.2, Figure 4"},{"comment":"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.","section":"§2.3, Theorem 2"},{"comment":"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.","section":"§3.1, Convention 2"},{"comment":"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.","section":"§2.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is clearly written and the combinatorial skeleton is promising, but the geometric core is missing. I would not reject on novelty grounds, but the revision must provide a rigorous embedding argument for Theorems 1 and 3, and a completed proof for Theorem 4 that accounts for the dummy clause vertices. The authors may also wish to consult the literature on topological graph drawing and non-crossing paths in non-planar drawings, since the required curve-routing arguments are likely standard in that area."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe one thing to know: this paper has a genuinely new reduction idea—3-SAT to non-crossing Hamiltonian path/cycle in embedded non-planar graphs, without any planarity-forcing gadgets. That is a real departure from the prior planar reductions, and if the construction works it gives a template for other non-crossing problems.\n\nWhat it does well: the concentric-ring and clause-column layout is clearly explained, and the converse direction (Theorem 2) uses a neat degree-counting argument to show any non-crossing Hamiltonian path must stay on one ring at a time. That part is plausible and, as far as I can tell, correct. The paper also gives explicit vertex counts and states its assumptions honestly.\n\nThe soft spot is exactly where the reader's report puts it: the non-crossing claim in the forward direction is asserted, not proven. Theorem 1 says the detour is 'directed inward' and therefore avoids crossings, but no coordinates or topological routing argument are given. The stress-test note gives a concrete scenario: when clause c_j is first satisfied at ring i, the path later uses edges from outer rings to c(k,j) that could cross the earlier segment to c(0,j) under a natural straight-line drawing. That is a real, specific gap. It may be fixable with a carefully chosen embedding or a curve-routing argument, but as written the central 'if' direction is unsupported. The cycle extension inherits the same problem and adds a table-driven case analysis that is even harder to verify without an explicit drawing.\n\nMinor issues: the non-planarity of the constructed graph is only argued for sufficiently large n and m, which is fine but should be stated as a condition. The self-citation to the authors' prior enumeration paper is not load-bearing, so no problem there.\n\nBottom line: this is a serious paper with a novel core, but it is not yet rigorous. A referee should ask for a formal proof of the non-crossing property—either explicit coordinates or a crossing-avoidance lemma for every detour type. Given the importance of the technique, I'd send it to review with that demand. I wouldn't cite it in its current form, but I'd bring it to a reading group to work through the geometry.","headline":"Novel direct reduction, but the non-crossing claim is unproven; deserves serious refereeing to settle the geometry.","tokens_in":8703,"tokens_out":3083,"would_cite":false,"duration_ms":27684,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68R10","05C45"],"pacs":[],"model":"deepseek-v4-flash","headline":"A direct 3-SAT reduction shows non-crossing Hamiltonian path and cycle are NP-complete in non-planar embedded graphs.","keywords":["non-crossing Hamiltonian path","non-crossing Hamiltonian cycle","NP-completeness","3-SAT reduction","non-planar graph embedding","computational geometry","graph drawing"],"falsifier":"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.","tokens_in":7675,"feed_emoji":"🧩","tokens_out":7044,"duration_ms":60398,"temperature":0.7,"pith_summary":"This paper tries to show that asking for a Hamiltonian path or cycle that does not cross itself is a hard problem for its own sake, not just because planar graphs are hard. Previous reductions to planar graphs make the path non-crossing automatically, so they cannot isolate the cost of the non-crossing constraint. The paper gives a direct many-one reduction from 3-SAT to the non-crossing Hamiltonian path problem and to the non-crossing Hamiltonian cycle problem in embedded graphs that are generally non-planar. If the reduction is correct, both problems are NP-complete, and the hardness is carried by the geometric restriction rather than by planarity-forcing gadgets.","feed_headline":"Non-crossing Hamiltonian paths are NP-complete in non-planar graphs","feed_subtitle":"The hardness comes from forbidding crossings on the path itself, not from planarity gadgets.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the standard NP-completeness framing for Hamiltonian path and cycle that motivates the problem.","marker":"[4]"},{"why":"Provides the base NP-complete problems and simplified reductions, including the Hamiltonian path reduction that the new construction adapts.","marker":"[5]"},{"why":"Shows planar Hamiltonian circuit NP-completeness, the prior result whose planarity gadgets the paper aims to bypass.","marker":"[6]"},{"why":"Shows planar digraph Hamiltonian cycle NP-completeness, a prior planar-hardness result that the cycle construction contrasts with.","marker":"[9]"}],"fun_headline_variants":["Non-crossing Hamiltonian path hardness proven without planar gadgets","Direct 3-SAT reduction shows non-crossing path NP-hardness","Planarity not to blame: non-crossing constraint makes path NP-hard","Forbidden crossings, not planarity, drive Hamiltonian path hardness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Non-crossing Hamiltonian path hardness proven without planar gadgets","Direct 3-SAT reduction shows non-crossing path NP-hardness","Planarity not to blame: non-crossing constraint makes path NP-hard","Forbidden crossings, not planarity, drive Hamiltonian path hardness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000539,"raw_usage":{"total_tokens":2523,"prompt_tokens":823,"completion_tokens":1700,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":439,"completion_tokens_details":{"reasoning_tokens":1627}},"tokens_in":439,"tokens_out":1700,"duration_ms":11531,"temperature":1.0,"reasoning_tokens":1627,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:21:58.168850+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Garey and David S","cited_arxiv_id":null,"evidence_quote":"Supplies the standard NP-completeness framing for Hamiltonian path and cycle that motivates the problem."},{"cited_title":"Garey, David S","cited_arxiv_id":null,"evidence_quote":"Provides the base NP-complete problems and simplified reductions, including the Hamiltonian path reduction that the new construction adapts."},{"cited_title":"Garey, David S","cited_arxiv_id":null,"evidence_quote":"Shows planar Hamiltonian circuit NP-completeness, the prior result whose planarity gadgets the paper aims to bypass."},{"cited_title":"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","cited_arxiv_id":null,"evidence_quote":"Shows planar digraph Hamiltonian cycle NP-completeness, a prior planar-hardness result that the cycle construction contrasts with."}],"review_version":1}