{"id":"140b7610-dcdd-4cb3-92de-8e26d4e64040","arxiv_id":"2502.01321","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Temporal cliques that are k-hop dismountable for any k are also dismountable in at most three hops, which simplifies the proof that every temporal clique has an O(n log n) spanner.","lead":"This paper studies 'dismountability', a method for shrinking temporal networks (networks whose links appear at certain times) without losing connectivity. It shows that only the very shortest dismountability cases matter, and that a known result about small spanners can be proved using this single idea.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4.1's equality between M− and {e−(v) : v∈V−} is false; this is the formal bridge to the bi-clique reduction and needs correction.","rationale":"The reader's weakest assumption focused on the simple/proper restriction and reliance on external theorems, but a close reading shows those are not where the main risk lies: the simple/proper reduction is standard for non-strict temporal paths, and the cited results are used appropriately. The single concrete formal error I found is in Corollary 4.1, whose equality between M− and {e−(v): v∈V−} is contradicted by an explicit non-{1,2}-hop dismountable clique. This is load-bearing in the sense that the corollary is the stated bridge to the bi-clique reduction; however, the error is patchable because the separate matching properties are what Section 4.1 actually needs. Theorem 3.7 and Corollary 3.8 survive close scrutiny, so the overall verdict remains CONDITIONAL: the paper should be accepted only after Corollary 4.1 is corrected and the reduction is re-stated in terms of the true matching properties.","tokens_in":15761,"tokens_out":39891,"duration_ms":336360,"concrete_test":"Re-derive Corollary 4.1 on the 4-node example above and verify that the two sets are indeed different. Then re-run the Section 4 reduction argument using only the two separate matching properties: {e−(v): v∈V+} is a perfect matching and {e+(v): v∈V−} is a perfect matching. If the O(n log n) spanner construction goes through unchanged without the false equality, the defect is local and CONDITIONAL acceptance stands with a correction requested. If the reduction implicitly relies on the equality, the proof of the recovery claim must be revised before acceptance.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Corollary 4.1 states that M− := {e−(v) : v∈V+} equals {e−(v) : v∈V−} and that M+ likewise equals {e+(v) : v∈V+}. This equality is false in general. Consider the 4-node temporal clique with V−={a,b}, V+={x,y} and labels ab=1, ax=2, by=3, ay=4, bx=5, xy=6. This labeling is simple and proper, and it satisfies Theorem 3.9(1) and (2): V− and V+ have the same size and partition V, and every cross edge is later than all adjacent E− edges and earlier than all adjacent E+ edges. Hence, by Theorem 3.9, it is not {1,2}-hop dismountable. But {e−(v): v∈V+} = {ax, by}, whereas {e−(v): v∈V−} = {ab}; these sets are not equal. The true content, which is sufficient for the reduction, is that each of {e−(v): v∈V+} and {e+(v): v∈V−} is a perfect matching between the two parts. As written, Corollary 4.1 overclaims, and Section 4 uses this corollary as the formal justification for the bi-clique reduction. If the equality is meant to support the 'prefixing/suffixing' argument after the reduction, that part of the proof needs to be re-derived using only the two matchings separately. The central collapse theorem (Theorem 3.7) and Corollary 3.8 appear sound; the error is localized to the presentation of the reduction, but it is a genuine correctness defect in a formal statement.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper revisits the dismountability technique for temporal cliques. It gives structural characterizations of cliques that are not 1-hop dismountable, not {1,2}-hop dismountable, and not {1,2,3}-hop dismountable, and proves that if a clique is k-hop dismountable for any k > 3 then it is already {1,2,3}-hop dismountable (Theorem 3.7). Based on this, the paper proposes a reduction from cliques to bi-cliques using only dismountability, recovering the O(n log n) temporal spanner bound. In a second part, it proves that recursively k-hop dismountable cliques are pivotable and introduces full-range temporal graphs, showing that full-range cliques are {1,2,3}-hop dismountable and full-range temporally connected graphs are pivotable.","tokens_in":16066,"tokens_out":22928,"duration_ms":196955,"significance":"If the main structural claims and reductions are correct, this is a valuable simplification of the known O(n log n) spanner construction for temporal cliques, and the structural characterization of minimal counterexamples to linear spanners is of independent interest. The paper is proof-oriented and does not rely on numerical fitting or black-box parameter tuning; its claims are derived from the definitions. The pivotability result connecting recursive dismountability to pivotability is a useful addition, and the full-range family is a genuinely new class with clean properties. However, several formal statements in the proof chain need correction before the paper can be considered reliable.","major_comments":[{"comment":"","section":"Section 4, Corollary 4.1"},{"comment":"","section":"Section 3.4, Theorem 3.7"},{"comment":"","section":"Section 3.5, Theorem 3.10"}],"minor_comments":[{"comment":"","section":"Abstract"},{"comment":"","section":"Section 3.4, Theorem 3.7 proof"},{"comment":"","section":"Section 5, Theorem 5.2 proof"},{"comment":"","section":"Section 5.1, Theorem 5.7 proof"},{"comment":"","section":"Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"The paper's core ideas appear sound and the issues identified are local in nature, but they are formal defects in load-bearing statements (Corollary 4.1, Theorem 3.7, and Theorem 3.10). I would encourage the authors to correct these points and resubmit; the paper is likely acceptable after a careful revision. No concerns about attribution or novelty beyond what is stated in the related-work section."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe real content of this paper is the collapse theorem (Theorem 3.7): if a temporal clique is k-hop dismountable for any k>3, it is {1,2,3}-hop dismountable. Combined with the characterizations of non-{1,2}- and non-{1,2,3}-hop dismountable cliques (Theorems 3.9 and 3.10), this gives a clean picture: only the 1,2,3 hierarchy matters. Corollary 3.8—any minimal counterexample to 4n spanners must be non-k-hop dismountable—is a nice by-product. The recovery of the O(n log n) bound using only dismountability is genuinely elegant, though it leans on the Angrick et al. bi-clique result.\n\nThe paper is honest about not resolving the O(n) question, and the structural theorems appear correct after careful reading. The proofs are mostly well-argued.\n\nThe soft spots are localized but real. Corollary 4.1 overclaims: it states M− := {e−(v): v∈V+} equals {e−(v): v∈V−}. That is false. A 4-node example suffices: V−={a,b}, V+={x,y}, with labels ab=1, ax=2, by=3, ay=4, bx=5, xy=6. This is simple, proper, and satisfies the Theorem 3.9 conditions, yet {e−(v): v∈V+}={ax,by} while {e−(v): v∈V−}={ab}. The same holds for M+. The reduction only needs the two sets to be perfect matchings between the parts, and the 'prefixing/suffixing' argument can be re-derived from that, but as written the formal statement is wrong and the subsequent paragraph is too terse to cover the gap. Also, Theorem 5.2's induction is sketched rather than fully written out, and Theorem 5.7's 'can be composed with it' needs a sentence more. These are presentation defects, not cracks in the main structural results.\n\nThe simple/proper assumption is standard and the paper defends it; I don't read that as a flaw.\n\nOverall: this deserves a serious referee. The collapse theorem and characterizations are worth publishing; they will be useful to anyone working on temporal spanners. The revision should fix Corollary 4.1 and tighten the two proofs mentioned. I'd accept it with major/minor revisions rather than desk-reject.","headline":"Clean structural collapse theorem for k-hop dismountability, but Corollary 4.1 overclaims an equality that is false; the bi-clique reduction needs a small repair.","tokens_in":16646,"tokens_out":9233,"would_cite":true,"duration_ms":71036,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C82","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Dismountability alone recovers the O(n log n) spanner bound for temporal cliques and characterizes any 4n counterexample.","keywords":["temporal graphs","temporal cliques","temporal spanners","dismountability","pivotability","dynamic networks","reachability","full-range labelings"],"falsifier":"Run an exhaustive search over all simple, proper labelings of temporal cliques on at most six vertices: if any clique is $k$-hop dismountable for some $k>3$ but has no $\\{1,2,3\\}$-hop dismountable node, Theorem 3.7 is false. An explicit single such clique would also refute the paper's main structural claim.","tokens_in":15538,"feed_emoji":"🕒","tokens_out":8901,"duration_ms":69716,"temperature":0.7,"pith_summary":"This paper tries to establish that one structural principle, dismountability, is enough to explain why every temporal clique has a sparse temporal spanner. It characterizes, in a necessary and sufficient way, the structure of a temporal clique that resists dismounting at 1, 2, or 3 hops, and proves that if a clique is $k$-hop dismountable for any $k>3$, then it is already $\\{1,2,3\\}$-hop dismountable. From this, the known $O(n \\log n)$ spanner bound follows through a single constructive algorithm that uses only dismountability. A by-product is that any minimal counterexample to a $4n$-edge spanner would have to be a clique that is not dismountable at any hop count. The paper also connects dismountability to pivotability and identifies full-range labelings as a family for which both properties hold.","feed_headline":"Temporal cliques: only 1-, 2-, 3-hop dismountability matters","feed_subtitle":"A single principle yields the O(n log n) spanner bound and pins down any 4n counterexample.","key_machinery":"The central object is the dismountability of a node $u$ in a temporal clique: if some node $v$ has $u$ as its earliest neighbor and some node $w$ has $u$ as its latest neighbor, then $u$ can be removed from the instance at the cost of keeping the two edges $uv$ and $uw$ in the spanner, and one can recurse on the smaller clique; $k$-hop dismountability relaxes 'earliest/latest neighbor' to temporal paths of length at most $k$. The argument is carried by the partition of vertices into $V^-$ (nodes that are earliest neighbors), $V^+$ (nodes that are latest neighbors), and $V^0$ (the rest), by the two perfect matchings $M^-$ and $M^+$ forced between $V^-$ and $V^+$ in non-$\\{1,2\\}$-hop-dismountable cliques, and by the label-order condition that forbids an intra-part edge whose label lies between the two incident matching-edge labels. This machinery shows exactly where a recursive dismounting gets stuck.","core_discovery":"The central claim is Theorem 3.7: for a simple, proper temporal clique, $k$-hop dismountability for any $k>3$ implies $\\{1,2,3\\}$-hop dismountability. Thus the only dismountability structure that can obstruct recursion is the hierarchy of 1-, 2-, and 3-hop failures. Combined with the bi-clique reduction of Angrick et al., this gives a proof that every temporal clique admits an $O(n \\log n)$-edge temporal spanner using dismountability alone, and any minimal counterexample to $4n$-edge spanners must be non-$k$-hop dismountable for every $k$ and satisfy the complete structural description of Theorem 3.10. The paper further shows that recursively $k$-hop dismountable cliques are pivotable, hence admit $2n-3$ spanners, and that full-range temporally connected graphs are pivotable.","pith_inferences":["If the $4n$ counterexample structure is ever shown impossible, the proof would likely come from analyzing non-$\\{1,2,3\\}$-hop dismountable cliques only; the paper's characterization narrows the search space to that class.","The paper's finding that full-range (large-lifetime) labelings are easy suggests hard instances are concentrated at small compressed lifetimes, so decomposing a labeling by lifetime could be a route toward an $O(n)$ bound.","The implication that recursive dismountability yields pivotability offers a possible unification: any recursively dismountable clique gets a linear spanner through a single pivot edge.","A testable extension is whether every temporal clique admits a 2-arch spanner (a maximal 2-degenerate footprint), as preliminary experiments in the paper suggest; if true, that would strengthen the evidence for linear-size spanners beyond dismountability."],"forward_implications":["Any temporal clique that is $k$-hop dismountable for $k>3$ is already $\\{1,2,3\\}$-hop dismountable, so no new dismountability structure appears beyond three hops.","The $O(n \\log n)$ spanner bound for temporal cliques follows constructively from dismountability alone, via a polynomial-time algorithm.","Every minimal counterexample to $4n$-edge spanners must be non-$k$-hop dismountable for all $k$ and must satisfy the complete structural description of Theorem 3.10.","Non-$\\{1,2\\}$-hop dismountable cliques reduce to temporal bi-cliques on the same vertex set, preserving the vertex count for later constant-factor studies.","Recursively $k$-hop dismountable cliques admit $2n-3$ edge spanners, and full-range temporally connected graphs admit $O(n)$ spanners via pivotability."],"supporting_citations":[{"why":"Defines dismountability and gives the original $O(n \\log n)$ spanner result that this paper revisits and reproves.","marker":"[13]"},{"why":"Supplies the one-sided dismountability recursion and the bi-clique reduction used to recover $O(n \\log n)$ using dismountability only.","marker":"[3]"},{"why":"Shows a pivot edge yields a $2n-3$ spanner, used to connect recursive dismountability to pivotability.","marker":"[10]"},{"why":"Establishes that temporal graphs need not admit spanning trees, motivating the search for sparse spanners in cliques.","marker":"[18]"},{"why":"Gives a quadratic lower bound for general temporal graphs, framing why the clique case is the interesting restriction.","marker":"[4]"}],"fun_headline_variants":["Only 1-, 2-, 3-hop dismountability shapes temporal cliques","Dismountability alone yields O(n log n) temporal spanners","Only 1-,2-,3-hop failures block spanner recursion","Minimal 4n-spanner counterexample must fail 1-2-3 hops"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire analysis assumes the standard reduction to temporal cliques in which every edge has exactly one time label and adjacent edges have different labels, because extra labels or equal adjacent labels are said only to increase reachability; if that reduction fails in the strict-path setting, the characterizations would not cover the general problem.","fun_headline_variants_meta":{"raw":{"variants":["Only 1-, 2-, 3-hop dismountability shapes temporal cliques","Dismountability alone yields O(n log n) temporal spanners","Only 1-,2-,3-hop failures block spanner recursion","Minimal 4n-spanner counterexample must fail 1-2-3 hops"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001613,"raw_usage":{"total_tokens":6528,"prompt_tokens":1161,"completion_tokens":5367,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":777,"completion_tokens_details":{"reasoning_tokens":5282}},"tokens_in":777,"tokens_out":5367,"duration_ms":36897,"temperature":1.0,"reasoning_tokens":5282,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T15:43:43.375335+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive search over all simple, proper labelings of temporal cliques on at most six vertices: if any clique is $k$-hop dismountable for some $k>3$ but has no $\\{1,2,3\\}$-hop dismountable node, Theorem 3.7 is false. An explicit single such clique would also refute the paper's main structural claim.","supporting_citations":[{"cited_title":"Peters, and Jason Schoeters","cited_arxiv_id":null,"evidence_quote":"Defines dismountability and gives the original $O(n \\log n)$ spanner result that this paper revisits and reproves."},{"cited_title":"How to reduce temporal cliques to find sparse spanners","cited_arxiv_id":null,"evidence_quote":"Supplies the one-sided dismountability recursion and the bi-clique reduction used to recover $O(n \\log n)$ using dismountability only."},{"cited_title":"Bui-Xuan, Afonso Ferreira, and Aubin Jarry","cited_arxiv_id":null,"evidence_quote":"Shows a pivot edge yields a $2n-3$ spanner, used to connect recursive dismountability to pivotability."},{"cited_title":"Kempe, J","cited_arxiv_id":null,"evidence_quote":"Establishes that temporal graphs need not admit spanning trees, motivating the search for sparse spanners in cliques."},{"cited_title":"On the size and the approximability of minimum temporally connected subgraphs","cited_arxiv_id":null,"evidence_quote":"Gives a quadratic lower bound for general temporal graphs, framing why the clique case is the interesting restriction."}],"review_version":1}