{"id":"f60cafda-f628-4cde-959c-d19da3c59000","arxiv_id":"1908.07447","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"C-shaped supergrid graphs are always Hamiltonian and almost always Hamiltonian connected; the exceptions are listed, and the longest path between any two vertices can be computed in linear time.","lead":"This paper gives a full characterization of when C-shaped supergrid graphs have a Hamiltonian cycle or a Hamiltonian path between two specified vertices, and presents a linear-time algorithm for the longest such path. It is an extension of the authors' earlier work on rectangular and L-shaped supergrid graphs to a class with a rectangular hole.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.5 is stated only for (c>2 or d>2), yet Theorem 3.6 needs the case a>1 with c>1 or d>1; the omitted c=2,d=1 and c=2,d=2 (and mirror) cases are not covered by Lemmas 3.3–3.4, so the Hamiltonian-path characterization is incomplete as written.","rationale":"The reader's conditional verdict already identifies the Lemma 3.5 statement mismatch, and my read agrees that this is a serious proof gap. I single out the c=2,d=1 and c=2,d=2 omissions because they are purely internal: no citation or external orientation property is needed to see that Theorem 3.6 uses Lemma 3.5 beyond its stated range. The flat-face orientation issue raised by the reader is also real, but it is partly supported by the canonical constructions in Lemma 2.1 and by the cited L-shaped algorithms, so it is less decisive for the central claim. The paper has no machine-checked formalization, and the prior L-shaped results in [41] are themselves an arXiv preprint, which increases the need for the internal case analysis to be explicit. The proposed brute-force test would settle whether the omitted cases actually contain counterexamples; if they do not, the concern remains a proof-completeness defect that a revision can address. This leaves the reader's CONDITIONAL verdict in place.","tokens_in":34096,"tokens_out":10479,"duration_ms":95023,"concrete_test":"Brute-force enumerate all C(m,n;k,l;c,d) with m,n≤7, a>1, and (c,d) ∈ {(2,1),(2,2),(1,2)}, over all endpoint pairs s,t, computing Hamiltonian path existence and comparing it with the predicate \"none of F1, F3, F7, F8, F9 holds\". Include the explicit omitted instance C(3,4;1,1;2,1). If any pair avoids F1, F3, F7, F8, F9 but has no Hamiltonian path, Theorem 3.6 is false; if all pass, the statement-level gap is a proof-completeness defect, and the authors must extend Lemma 3.5 (or add a lemma) covering d=2 and c=2 explicitly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3.5 is the only sufficiency argument in Theorem 3.6 for the block a>1 with c>1 or d>1. Its statement concludes existence only \"when a≥2 and (c>2 or d>2)\", but Theorem 3.6 requires existence for all a≥2 with c>1 or d>1 after excluding F1, F3, F7, F8, and F9. The missing configurations, for example C(3,4;1,1;2,1) with a=2, c=2, d=1, k=l=1, and the symmetric c=2,d=2 cases, do not fall under Lemma 3.3 (a=1) or Lemma 3.4 (c=d=1). The proof of Lemma 3.5 only assumes d>1 and never explains why d=2 or c=2 is excluded; its Cases 2 and 3 are delegated to \"similar arguments\" from Lemma 3.4, whose c=d=1 decomposition is structurally different. Consequently the iff statement is not proven for a nonempty parameter family, and the O(mn) longest-path theorem inherits the same unproved cases. This is internal to the paper's proof structure; it is not an objection to the plausibility of the result.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Hamiltonian cycles, Hamiltonian (s,t)-paths, and longest (s,t)-paths in C-shaped supergrid graphs, i.e., rectangular supergrid graphs from which a rectangular block has been removed so that the remaining shape is C-like. The main results are: (Theorem 3.1) a C-shaped supergrid graph has a Hamiltonian cycle iff it does not satisfy condition (F6); (Theorem 3.6) a Hamiltonian (s,t)-path exists iff the pair (C(m,n;k,l;c,d),s,t) avoids conditions (F1), (F3), (F7), (F8), and (F9); and (Theorem 4.5) a longest (s,t)-path can be computed in O(mn) linear time. The proofs are constructive and proceed by separating the graph into rectangular and L-shaped supergrid subgraphs, applying previously established Hamiltonian results, and gluing the resulting cycles and paths via Proposition 2.5. The longest-path section derives upper bounds for the forbidden cases and gives matching constructions.","tokens_in":34333,"tokens_out":6550,"duration_ms":64766,"significance":"If the results are correct, the paper provides a complete characterization of Hamiltonicity and Hamiltonian connectivity for a class of supergrid graphs with a hole, and it gives the first linear-time algorithm for the longest (s,t)-path problem in this class. This is a meaningful step beyond the previously solved rectangular and L-shaped cases, and it has concrete applications to embroidery and 3D-printing trace optimization. The paper is constructive and does not rely on numerical fitting or data-dependent parameters; it uses prior published theorems for rectangular and L-shaped supergrid graphs as building blocks. However, the proof is an extensive case analysis with many subcases delegated to figures, 'similar arguments', and 'simple checks', which makes verification difficult. More importantly, at least one parameter range needed by Theorem 3.6 is not actually covered by the stated Lemma 3.5, and the gluing arguments repeatedly assume an oriented face-placement property that is not stated in the cited prior results. These issues make the central characterization incomplete as written.","major_comments":[{"comment":"Lemma 3.5 is stated for graphs with c > 1 or d > 1, but its conclusion is restricted to 'a >= 2 and (c > 2 or d > 2)'. Theorem 3.6 then invokes Lemma 3.5 for the whole range c > 1 or d > 1. The cases c = 2 with d = 1, and c = 2 with d = 2, together with their mirrors, are not covered by Lemma 3.3 (which requires a = 1) or by Lemma 3.4 (which requires c = d = 1). The proof of Lemma 3.5 assumes without loss of generality that d > 1 and never explains why the cases with d = 1 and c = 2 should be excluded. For example, the graph C(3,4;1,1;2,1) has a = 2, c = 2, d = 1, and for endpoints not covered by (F7) it lies in the domain of Theorem 3.6 but outside the stated hypothesis of Lemma 3.5. Thus the if direction of the Hamiltonian-path characterization is not proven for a nonempty family of inputs, and Theorem 4.5 inherits the same gap. The lemma needs to be extended to the full range c > 1 or d > 1, or the theorem must be split with separate arguments for the missing cases.","section":"Section 3, Lemma 3.5 and Theorem 3.6"},{"comment":"Several gluing steps require a stronger property than what the cited theorems state. For instance, in Lemma 3.4, Case 2.1.1, the proof asserts that R2 contains a Hamiltonian (s,t)-path P2 'in which one edge e2 is placed to face R1' and that R1 contains a Hamiltonian cycle HC1 'such that its one flat face is placed to face R2'; analogous assertions occur in Lemma 3.5, Cases 1.1 and 1.2, and in Lemma 4.4, Cases 4 and 6. However, Theorem 2.8 and Theorem 2.9, as stated in this paper, only assert the existence of a Hamiltonian path and a Hamiltonian cycle, respectively, and Lemma 2.4 gives an oriented-edge property only for rectangular graphs, not for L-shaped graphs. Because the concatenation via Proposition 2.5(2) requires two edges e1 ≈ e2, the oriented face-placement property is load-bearing. If the prior constructions in [41] do indeed always provide such an orientation, the paper should either prove this or cite the exact statements; otherwise the gluing construction may fail.","section":"Section 3, Lemmas 3.4–3.5 and Proposition 2.5"},{"comment":"The control flow of Algorithm 4.1 is incorrect for inputs that satisfy a forbidden condition. Step 1 outputs a Hamiltonian path whenever a = 1, and Steps 2 and 3 behave similarly for a > 1, without first checking whether (C,s,t) satisfies (F1), (F3), (F7), (F8), or (F9). Step 4 is therefore unreachable exactly for the inputs it is meant to handle. For example, if a = 1 and sy, ty <= c, condition (F9) holds and no Hamiltonian (s,t)-path exists, yet Step 1 would invoke Lemma 3.3 and return a Hamiltonian path. The guards in Steps 1–3 need to include the condition that none of the forbidden conditions holds, or Step 4 must be evaluated before the constructive lemmas are applied.","section":"Section 4, Algorithm 4.1"}],"minor_comments":[{"comment":"The definition of p and q in Case 2.2 has a final 'otherwise' branch that is ambiguous when more than one of the preceding conditions fails; the four combinations should be spelled out explicitly.","section":"Section 3, Lemma 3.4, Case 2.2"},{"comment":"The proof delegates Cases 2 and 3 to 'similar arguments' from Lemma 3.4, but the decomposition in Lemma 3.5 is structurally different because R1 is a rectangular graph rather than an L-shaped graph; the required arguments should be given rather than only referenced.","section":"Section 3, Lemma 3.5, Cases 2 and 3"},{"comment":"The proof of the necessity of (F7) says that existence is checked 'by inspecting all cases of Fig. 12(d)', but the figure appears to show only a representative configuration; a complete enumeration or a short parity/cut argument would make the necessity proof more transparent.","section":"Section 3, Lemma 3.2, condition (F7)"},{"comment":"In the proof of Lemma 4.3, the text reads 'For (FC14) and (F15)' where the second label should be (FC15); this typo should be corrected.","section":"Section 4, Lemma 4.3"},{"comment":"The proof of Lemma 4.1 is stated as 'straightforward, see Fig. 21', but the upper-bound claims in (FC7) and (FC8) are used later in Theorem 4.5; a short justification for why no path can use vertices outside the indicated L-shaped subgraphs would improve the verifiability.","section":"Section 4, Lemma 4.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript addresses an interesting and plausible result, and the constructive approach is natural. However, the missing parameter cases in Lemma 3.5 are a genuine gap in the proof of the central characterization, and the oriented face-placement property in the gluing arguments needs to be either proven or precisely referenced. The Algorithm 4.1 control-flow issue is easy to fix but should be corrected. I would be willing to re-review after these points are addressed; the authors may also consider adding more detailed proofs for the delegated 'similar arguments' subcases, since the current level of detail makes independent verification very time-consuming."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this is a real result, not a repackaging, but the main sufficiency proof has a gap in Lemma 3.5 that needs to be closed before I'd trust Theorem 3.6 as stated. The authors characterize Hamiltonian cycles, Hamiltonian (s,t)-paths, and longest paths for C-shaped supergrid graphs—the first time this class with a boundary-touching rectangular hole gets treated. The techniques are inherited from their rectangular and L-shaped supergrid work, so novelty is incremental, but the class is nontrivial and the linear-time longest path algorithm is a concrete payoff. No fitting, no invented parameters; the self-citations point to genuinely prior published results, and I don't see circularity.\n\nThe soft spots are in the proof presentation. Lemma 3.5 assumes c > 1 or d > 1 but concludes existence only when c > 2 or d > 2. Those cannot both be right. Since Theorem 3.6 applies Lemma 3.5 to every a > 1 case not covered by Lemma 3.4, the c=2,d=1 and c=2,d=2 (and mirrored) configurations are left without a stated sufficiency argument. The proof itself actually seems to handle d=2 in Case 1.1 and Case 1.2, and the WLOG d > 1 symmetry covers c=2,d=1 after rotation, which makes me think this is a fixable typo in the lemma statement rather than a false theorem. But as written, the iff in Theorem 3.6 is not established for a nonempty family. The authors need to restate Lemma 3.5 cleanly and add a sentence explaining why the d=2 cases inside it are covered.\n\nSecond soft spot is heavier delegation than I'd like. Several subcases end with 'a simple check shows' or 'by similar arguments' and the figures carry the proof. In particular, the repeated claim that canonical cycles/paths can be oriented with a flat face toward a designated separator edge is asserted from earlier algorithms, but not stated as a lemma or proven here. That property is load-bearing for the gluing operation, and the authors should make the citation exact or add the missing statement. These are layout issues in a long case analysis, and I don't think they sink the result, but a referee would have to do real work to verify all of them.\n\nWho is this for? Researchers working on Hamiltonian/longest paths in grid-like graphs, especially the supergrid literature. The applications to embroidery/3D printing stitching are plausible but not developed. I'd send it to a serious referee; the gap is specific and likely fixable. My recommendation: conditional acceptance, with the Lemma 3.5 statement fixed and the c=2 cases explicitly walked through.","headline":"A genuine first treatment of C-shaped supergrid graphs that deserves referee time, but the main sufficiency lemma has a stated parameter gap (c=2,d=1 and c=2,d=2) that needs to be fixed before Theorem 3.6 is fully proven.","tokens_in":34923,"tokens_out":4161,"would_cite":false,"duration_ms":40528,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C45","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"C-shaped supergrid graphs: Hamiltonian paths fully classified","keywords":["Hamiltonian path","Hamiltonian cycle","Hamiltonian connectivity","longest path","supergrid graphs","C-shaped supergrid graphs","linear-time algorithm","cut vertex"],"falsifier":"Check the smallest nontrivial case of Lemma 3.4, the C-shaped graph $C(4,4;1,2;1,1)$ with $s=(2,2)$ and $t=(2,3)$: it has 14 vertices, and an exhaustive enumeration will either find a Hamiltonian $(s,t)$-path or not. If none exists, the constructive proof of Theorem 3.6 fails for that case; if one exists, the claimed gluing pattern is corroborated on the minimal example.","tokens_in":33831,"feed_emoji":"🧵","tokens_out":7057,"duration_ms":69020,"temperature":0.7,"pith_summary":"This paper proves the exact conditions under which a C-shaped supergrid graph—a rectangular grid of vertices with a rectangular block removed from one side, leaving a C-like shape—contains a Hamiltonian cycle and a Hamiltonian path between two prescribed vertices. It then gives an algorithm that constructs a longest path between any two distinct vertices in linear time in the number of cells. The main characterization is a short list of forbidden configurations: one cuts off a degree-one vertex or separates the endpoints, and the other four are small endpoint patterns that force a path to miss a vertex. If the results are correct, they settle the Hamiltonian and longest-path problems for this class of supergrid graphs with a rectangular hole, a step beyond the previously solved rectangle and L-shaped cases. Because Hamiltonian paths in general supergrid graphs are NP-complete, the positive result is a structural gain rather than a routine extension.","feed_headline":"C-shaped supergrid graphs: Hamiltonian paths classified in linear time","feed_subtitle":"The paper lists all forbidden endpoint patterns and gives a linear-time algorithm for the longest path between any two vertices.","key_machinery":"The load-bearing objects are canonical Hamiltonian cycles and paths: Hamiltonian cycles of rectangular supergrid graphs that follow the boundary on three sides (flat faces) and deviate on one side (a concave face), and rectangular Hamiltonian $(s,t)$-paths that keep at least one boundary edge on each side. The proofs partition the C-shaped graph by vertical and horizontal separations into rectangular and L-shaped supergrid subgraphs, then glue Hamiltonian cycles or paths of the pieces using Proposition 2.5: two cycles, or a cycle and a path, with parallel edges across a separator can be spliced into one cycle or path. The flat-face orientation is what supplies those parallel edges. The forbidden conditions are collected from the cut-vertex/vertex-cut obstruction of Lemma 2.2 and from the endpoint patterns that survive because a too-narrow arm of the C cannot be traversed without revisiting a vertex.","core_discovery":"The paper's central claim is Theorem 3.6: a C-shaped supergrid graph $C(m,n;k,l;c,d)$ has a Hamiltonian $(s,t)$-path if and only if the pair does not satisfy any of five conditions (F1), (F3), (F7), (F8), and (F9). Condition (F1) says $s$ or $t$ is a cut vertex, or $\\{s,t\\}$ separates the graph; (F3) says there is a degree-one vertex other than $s,t$; (F7), (F8), and (F9) are explicit endpoint placements in narrow arms of the C. The paper also proves (Theorem 3.1) that the graph is Hamiltonian if and only if it avoids condition (F6), namely a one-column arm or any degree-one vertex. On top of these, Theorem 4.5 states that a longest $(s,t)$-path can be found in $O(mn)$ time. In the authors' phrasing, C-shaped supergrid graphs are Hamiltonian except when an arm is one column wide or a vertex has no way through, and Hamiltonian connected except for the five listed endpoint patterns.","pith_inferences":["If the flat-face orientation property holds in full generality, the same separation-and-gluing method should extend to other polyomino-shaped supergrid graphs whose rectangular decomposition yields at most L-shaped pieces, such as S-shaped or E-shaped holes, giving analogous if-and-only-if characterizations.","The forbidden endpoint lists in (F7), (F8), and (F9) all look like local separator obstructions; a natural conjecture is that every non-Hamiltonian-connected supergrid class fails only through cut vertices, degree-one vertices, or tiny endpoint-separator patterns of this kind.","A concrete stress test for the construction is to implement Lemma 3.4 on the smallest case, $C(4,4;1,2;1,1)$ with $s=(2,2)$ and $t=(2,3)$, and compare the constructed path against an exhaustive enumeration of all 14-vertex Hamiltonian $(s,t)$-paths.","The longest-path upper bounds in Lemmas 4.1–4.3 are expressed through already-solved rectangular and L-shaped instances; this suggests a recursive scheme for longer chains of holes, where each new hole adds one more level of previously solved subproblems."],"forward_implications":["Every C-shaped supergrid graph with arms at least two columns wide and no degree-one vertex has a Hamiltonian cycle.","A Hamiltonian path between two prescribed endpoints exists in all but the five explicitly listed forbidden endpoint placements; outside those, the proof actually constructs the path.","A longest path between any two distinct vertices can be output in time linear in the number of vertices, not merely decided.","The same theorem yields an optimal stitching trace for computer embroidery on C-like shapes and a minimum printing trace for 3D printing a C-like component, the applications named in the paper.","Because the conditions are if-and-only-if, they give a linear-time certificate: checking the finite list of forbidden configurations decides Hamiltonicity or Hamiltonian connectivity."],"supporting_citations":[{"why":"Supplies canonical Hamiltonian cycles in rectangular supergrid graphs, which seed the gluing constructions used throughout the proofs.","marker":"[22]"},{"why":"Supplies canonical Hamiltonian $(s,t)$-paths in rectangular supergrid graphs and the cut-vertex/vertex-cut obstruction behind condition (F1).","marker":"[24]"},{"why":"Supplies the L-shaped supergrid Hamiltonian-path, Hamiltonian-cycle, and longest-path results that the C-shaped proofs reduce to.","marker":"[41]"},{"why":"Supplies Theorem 2.9 on Hamiltonian cycles in L-shaped supergrid graphs, used when gluing cycles into C-shaped graphs.","marker":"[27]"},{"why":"Supplies Lemma 2.2, the general assertion that condition (F1) forces absence of a Hamiltonian $(s,t)$-path in any supergrid graph.","marker":"[36]"}],"fun_headline_variants":["C-shaped supergrids: linear-time longest path algorithm","C-shaped supergrid graphs: exact Hamiltonian path rules","C-shaped supergrids: Hamiltonian connectivity decided in O(mn)","C-shaped supergrid graphs: all forbidden Hamiltonian path patterns","C-shaped supergrids: longest path found in linear time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proofs repeatedly assume that canonical Hamiltonian cycles and paths in rectangular and L-shaped supergrid graphs can always be oriented so that a flat face lies along a chosen separator edge; that orientation capability is asserted rather than explicitly proven in the cited constructions, and the gluing steps collapse without it.","fun_headline_variants_meta":{"raw":{"variants":["C-shaped supergrids: linear-time longest path algorithm","C-shaped supergrid graphs: exact Hamiltonian path rules","C-shaped supergrids: Hamiltonian connectivity decided in O(mn)","C-shaped supergrid graphs: all forbidden Hamiltonian path patterns","C-shaped supergrids: longest path found in linear time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000819,"raw_usage":{"total_tokens":3627,"prompt_tokens":1030,"completion_tokens":2597,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":646,"completion_tokens_details":{"reasoning_tokens":2514}},"tokens_in":646,"tokens_out":2597,"duration_ms":16353,"temperature":1.0,"reasoning_tokens":2514,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:49:58.523806+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check the smallest nontrivial case of Lemma 3.4, the C-shaped graph $C(4,4;1,2;1,1)$ with $s=(2,2)$ and $t=(2,3)$: it has 14 vertices, and an exhaustive enumeration will either find a Hamiltonian $(s,t)$-path or not. If none exists, the constructive proof of Theorem 3.6 fails for that case; if one exists, the claimed gluing pattern is corroborated on the minimal example.","supporting_citations":[{"cited_title":"Hung, C.C","cited_arxiv_id":null,"evidence_quote":"Supplies canonical Hamiltonian cycles in rectangular supergrid graphs, which seed the gluing constructions used throughout the proofs."},{"cited_title":"Hung, C.F","cited_arxiv_id":null,"evidence_quote":"Supplies canonical Hamiltonian $(s,t)$-paths in rectangular supergrid graphs and the cut-vertex/vertex-cut obstruction behind condition (F1)."},{"cited_title":"The Hamiltonicity, Hamiltonian Connectivity, and Longest (s, t)-path of L-shaped Supergrid Graphs","cited_arxiv_id":"1904.02581","evidence_quote":"Supplies the L-shaped supergrid Hamiltonian-path, Hamiltonian-cycle, and longest-path results that the C-shaped proofs reduce to."},{"cited_title":"Hung, J.L","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 2.9 on Hamiltonian cycles in L-shaped supergrid graphs, used when gluing cycles into C-shaped graphs."},{"cited_title":"Keshavarz-Kohjerdi, A","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 2.2, the general assertion that condition (F1) forces absence of a Hamiltonian $(s,t)$-path in any supergrid graph."}],"review_version":1}