{"id":"15d679b9-d070-4c36-ae4f-cfc47be84908","arxiv_id":"1908.01524","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Cactus metrics, metrics realizable by cactus graphs, have unique optimal realizations and can be recognized in cubic time.","lead":"This paper introduces cactus metrics, distances that can be realized as shortest paths on a cactus-shaped graph, and proves each one has a single most efficient graph drawing. It also gives a fast algorithm to recognize these metrics and build that drawing.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 7's algorithm can output a minimal cycle with a slack vertex as an \"optimal\" realization, so the O(n^3) recognition/realization algorithm of Theorem 8 is incorrect as stated.","rationale":"The reader identified the compactification lemma in Theorem 5 as the weakest assumption. A careful reading of the compactification operation suggests that assertion is actually sound: on the modified cycle, the two neighbours of the removed slack vertex retain their previous slack status, the new vertex is not slack, and no other vertex can become slack because adjacent pairs on the complementary arc sum to at most the new cycle's half-length. So the uniqueness theorem is likely correct. However, the paper's second central claim, the polynomial-time recognition and realization algorithm, is not correct as written. Lemma 7 confuses minimality of a cycle with optimality, and the 4-point metric constructed above is a concrete counterexample: the algorithm outputs a minimal but non-optimal cycle. This is a sharper, demonstrable failure than the proof gap the reader flagged, and it invalidates Theorem 8 as stated. The flaw is likely repairable by adding a no-slack check in Step 4 and repairing the proof, but the current manuscript's algorithmic claim does not hold, so the verdict should move from CONDITIONAL to REJECT for this version.","tokens_in":7009,"tokens_out":34763,"duration_ms":377052,"concrete_test":"Implement Lemma 7 exactly as written and run it on the 4-point metric with D12=D23=10, D34=D41=7, D13=14, D24=17. If the algorithm returns the 4-cycle (v3,v4,v1,v2) with edge weights 7,7,10,10, the lemma is false as stated. Independently verify non-optimality by checking that the 5-vertex cactus with cycle edges v1-v4, v4-v3, v3-v', v'-v1 each of weight 7 and pendant edge v2-v' of weight 3 realizes the same metric with total weight 31 < 34. The proposed fix to test is to replace Step 4's minimality check with a no-slack check, i.e., verify d(v_{i-1},v_i)+d(v_i,v_{i+1})=d(v_{i-1},v_{i+1}) for every consecutive triple, including the pairs involving v0 and v_{n-1}; with that fix, the algorithm should reject this input.","verdict_should_be":"REJECT","load_bearing_attack":"The recognition half of the paper breaks at Lemma 7. Step 4 of the algorithm checks only that the constructed cycle is a minimal realization, but Theorem 3 says a minimal cycle is optimal iff it has no slack vertex; a minimal cycle can have slack. Concretely, take X={v1,v2,v3,v4} with distances d(v1,v2)=d(v2,v3)=10, d(v3,v4)=d(v4,v1)=7, d(v1,v3)=14, d(v2,v4)=17. This metric is realized minimally by the 4-cycle (v1,v2,v3,v4), and v2 is slack because 10+10>14. Running Lemma 7 can start with closest pair (v3,v4), then extend through v1, then v2, and close the same 4-cycle; Step 4's minimality check passes, so the cycle is output as optimal. Its total weight is 34, but the 5-vertex cactus with cycle edges all of weight 7 and pendant edge v2-v' of weight 3 has total weight 31 and realizes the same metric. Thus the output is not optimal, and there is in fact no optimal cycle realization. The lemma's proof asserts the constructed cycle \"satisfies the equation in Theorem 3,\" but the equation is never checked at the two endpoint vertices v0 and v_{n-1} of the growing path, so the assertion is false. Since Theorem 8 invokes Lemma 7 for every block, the recognition algorithm is incorrect as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces cactus metrics, i.e. finite metric spaces that can be realized by an edge-weighted cactus graph in which every vertex of degree at most two is labeled by a point of the space. The two main claims are: (i) Theorem 5, that every cactus metric has a unique optimal realization, which is presented as a generalization of the classical uniqueness theorem for tree metrics; and (ii) Theorem 8, that there is an O(n^3) algorithm that decides whether a given metric is a cactus metric and, if so, constructs its optimal realization. Section 2 reviews known results on tree metrics and cyclelike metrics, including Theorem 3, which characterizes when a cycle is an optimal realization. Section 3 proves Theorem 5 by a compactification operation that is asserted to remove slack vertices from cycles while preserving minimality. Section 4 gives Lemma 7, an O(n^2) algorithm for recognizing cyclelike metrics with an optimal cycle realization, and Theorem 8, which reduces the cactus recognition problem to the cyclelike case via the Hertz-Varone decomposition into blocks.","tokens_in":7366,"tokens_out":24027,"duration_ms":236425,"significance":"If correct, the uniqueness result for optimal realizations of cactus metrics is a natural and valuable extension of the classical Hakimi-Yau theorem for tree metrics, and the algorithmic result would give the first polynomial-time recognition procedure for a nontrivial class of graph-realizable metrics beyond trees. The paper also carries a genuine algorithmic ambition: it gives a concrete O(n^3) procedure with a stated complexity analysis. However, two load-bearing parts of the paper are not established as written. The compactification proof in Theorem 5 rests on an unproved assertion, and Lemma 7, which is the engine of the recognition algorithm, is demonstrably incorrect: its Step 4 checks only minimality, while optimal cycles are characterized by the stronger no-slack condition. The counterexample in the major comments shows that the algorithm can output a minimal but non-optimal cycle as an 'optimal realization'. These issues affect the central claims of both the theoretical and the algorithmic parts, although they appear to be repairable.","major_comments":[{"comment":"The correctness argument for Lemma 7 is false because Step 4 checks only that the constructed cycle is a minimal realization, whereas Theorem 3 requires the stronger no-slack condition d(v_{i-1},v_i)+d(v_i,v_{i+1})=d(v_{i-1},v_{i+1}) at every vertex of the cycle. A concrete counterexample is the metric on X={a,b,c,d} with d(a,b)=d(b,c)=10, d(c,d)=d(d,a)=7, d(a,c)=14, and d(b,d)=17. The 4-cycle a-b-c-d-a with edge weights 10,10,7,7 realizes this metric and is minimal, since removing any edge leaves a path much longer than the distance between its endpoints; however it is not optimal, because b is a slack vertex in the sense defined before Lemma 4. The cycle has total weight 34, while the X-cactus consisting of the 4-cycle a-b'-c-d-a with all edges of weight 7 and the pendant edge b'-b of weight 3 has total weight 31 and realizes the same metric. The algorithm can output the non-optimal 4-cycle: starting from the closest pair (c,d), Step 2 appends a because 7+d(d,a)=d(c,a), then appends b because d(d,a)+d(a,b)=d(d,b), and Step 4's minimality check passes. Thus Lemma 7 incorrectly reports that an optimal cycle realization exists, and Theorem 8, which invokes Lemma 7 for every block, can output a non-optimal cactus. Step 4 should test the no-slack equation at every vertex, including the two endpoint vertices v0 and v_{n-1}, and the converse direction must be reproved with that stronger check.","section":"Section 4, Lemma 7 and Theorem 8"},{"comment":"The compactification operation is the entire engine of the uniqueness proof, but the assertion 'As can be easily verified, G' is an X-cactus that is a minimal realization of (X,d) with a strictly smaller number of slack vertices than G' is not proved. One must show that G' still realizes the metric d, that no other cycle of G gains a new slack vertex during the operation, that the resulting graph is indeed minimal, and that iterating the operation terminates at a realization with no slack vertex rather than cycling through newly created 3-cycles or losing the X-cactus property. The initial reduction 'we can always replace a 3-cycle with a tree' is likewise stated without a proof in the setting where the 3-cycle is attached to the rest of the graph. Since the conclusion 'we will eventually obtain an X-cactus that realizes (X,d) without a slack vertex, which must be the unique optimal realization' depends entirely on this termination and preservation argument, the proof of Theorem 5 is incomplete as written.","section":"Section 3, proof of Theorem 5"}],"minor_comments":[{"comment":"The proof of Proposition 6 is only a sketch: the sentence 'any v in V(C) minus {v_{i-1},v_i,v_{i+1}} is not slack' requires a case analysis on the two arcs of the cycle, and the 'similar argument' for the case where v_{i-1} or v_{i+1} is slack is not spelled out. Please expand this proof for readability.","section":"Section 3, Proposition 6"},{"comment":"Step 4 of the algorithm says to check whether the constructed cycle is a minimal realization, but the paper does not describe how this check is carried out. Since the complexity claim depends on this step taking O(n^2), a brief explanation of the procedure would be helpful.","section":"Section 4, Lemma 7"},{"comment":"The caption uses the labels v3' and v4' but the three panels are not all annotated consistently; please label the new vertices in every panel so that the compactification sequence can be followed.","section":"Figure 2"},{"comment":"Reference [9] is cited as a conference program; if a peer-reviewed or more permanent version exists, it would be preferable to cite that instead.","section":"Introduction and references"}],"recommendation":"major_revision","confidential_remarks":"The counterexample to Lemma 7 is concrete and easy to reproduce, and it invalidates the algorithmic claim as stated. The compactification proof in Theorem 5 also needs to be written out in full. I do not see grounds to doubt the novelty of the cactus-metric concept or the plausibility of the uniqueness theorem, and both problems appear fixable within the scope of the paper, but the current version should not be published until these two load-bearing issues are resolved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe main theoretical result — Theorem 5, the unique optimal realization for cactus metrics — is a natural and worthwhile generalization of the classical Hakimi–Yau theorem for tree metrics. The block decomposition and slack-vertex analysis are sensible, and Proposition 6 (at most two adjacent slack vertices on a cycle) is a neat observation. If the compactification step can be made rigorous, the uniqueness result should hold.\n\nBut the algorithmic half is not correct as stated. Lemma 7’s algorithm only checks minimality in Step 4; minimality does not imply optimality for cycles. Here is a concrete counterexample. Let X = {v1,v2,v3,v4} with distances d12 = d23 = 10, d34 = d41 = 7, d13 = 14, d24 = 17. The 4-cycle v1-v2-v3-v4-v1 with edge weights 10, 10, 7, 7 realizes the metric and is minimal (each edge is necessary), but v2 is slack because 10+10 > 14, so the cycle is not optimal; its total weight is 34. A cactus with cycle v1-v4-v3-v'-v1 (all four edges weight 7) and pendant edge v2-v' of weight 3 realizes the same metric with total weight 31. The algorithm in Lemma 7 can start with the closest pair {v3,v4}, extend through v1 and v2, and produce exactly that non-optimal 4-cycle; Step 4 passes because the cycle is minimal. Hence Lemma 7 can output a non-optimal cycle, and the proof’s claim that the constructed cycle satisfies the equation in Theorem 3 is false. Theorem 8 inherits this error, so the O(n^3) recognition/realization algorithm is incorrect as written.\n\nThere are also proof gaps in Theorem 5: the compactification operation is asserted to preserve minimality and reduce slack vertices “as can be easily verified,” without proof. That step is load-bearing, and the 3-cycle replacement claim is similarly quick. These are addressable, but they are real gaps.\n\nThe citation pattern looks fair; prior work by Hakimi–Yau, Imrich et al., and Hertz–Varone is used appropriately, and there is no circularity.\n\nBottom line: the uniqueness result deserves refereeing and may well be correct, but the paper needs major revision to the algorithmic section and a fuller proof of compactification. I would send it to peer review, but I would not cite the algorithm in its current form.","headline":"The uniqueness theorem for cactus metrics is a natural and likely correct generalization of tree metrics, but the O(n^3) recognition algorithm is broken by a concrete counterexample and the compactification proof has serious gaps.","tokens_in":7831,"tokens_out":8796,"would_cite":false,"duration_ms":75767,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C05","05C12","92B10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every cactus metric has a unique optimal realization, and there is a cubic-time algorithm to recognize it and build that realization.","keywords":["cactus metric","X-cactus","metric realization","optimal realization","phylogenetic network","cyclelike metric","cutpoint decomposition","unique realization"],"falsifier":"Apply the compactification, as prescribed in the proof, to the 4-cycle with edge weights $1,2,1,1$ in cyclic order and the slack vertex $v_2$; the paper predicts the new graph still realizes the same metric and has fewer slack vertices. Computing all shortest-path distances before and after, and counting slack vertices, directly tests the local step on which Theorem 5 depends.","tokens_in":6822,"feed_emoji":"🌵","tokens_out":10281,"duration_ms":98642,"temperature":0.7,"pith_summary":"The paper introduces cactus metrics, finite metrics that arise as shortest-path distances on weighted cactus graphs—connected graphs in which every edge lies on at most one cycle. Its main result is that every cactus metric has a unique optimal realization, a weighted cactus of minimum total edge weight realizing the metric, extending the classical uniqueness theorem for tree metrics. It also gives an $O(n^3)$ algorithm that decides whether a given metric is a cactus metric and, if it is, constructs the unique optimal realization. If correct, this enlarges the family of metrics with a canonical, easy-to-visualize minimal graph representation, which matters for distance-based phylogenetic network reconstruction and similar data-analysis settings.","feed_headline":"Every cactus metric has a unique optimal realization","feed_subtitle":"A new O(n³) algorithm detects these tree-like metrics and builds their one minimal weighted cactus.","key_machinery":"The key mechanism is the slack-vertex compactification. For a cycle $v_1,\\dots,v_m$ in a minimal realization, compactifying $v_i$ replaces the two incident edges $\\{v_{i-1},v_i\\}$ and $\\{v_i,v_{i+1}\\}$ by three edges through a new vertex $v'_i$ with weights $\\Delta_{i-1},\\Delta_i,\\Delta_{i+1}$, where each $\\Delta$ is half the difference of the three relevant pairwise distances; the operation preserves the induced metric and lowers the number of slack vertices. Around this, the proof uses Theorem 3's criterion that an optimal cycle has no slack vertex, and a metric cutpoint decomposition that splits a metric into single-block components, each of which is either a tree or a cyclelike metric. The decomposition is what turns the local cycle check into a global recognition algorithm.","core_discovery":"The central claim is Theorem 5: if $d$ is a cactus metric on a finite set $X$, then there exists an $X$-cactus—a cactus in which every vertex of degree at most two is labeled by an element of $X$—that is the unique optimal realization of $(X,d)$. The proof takes any minimal realization and repeatedly applies a local 'compactification' operation at slack vertices of its cycles. A vertex $v_i$ on a cycle is slack when $d(v_{i-1},v_i)+d(v_i,v_{i+1})>d(v_{i-1},v_{i+1})$, and a cycle is optimal precisely when it has no slack vertices (Lemma 4). Each compactification reduces the number of slack vertices, so, after finitely many steps, one reaches a realization with no slack vertices; a block-decomposition result then shows this realization is the unique optimal one. The paper combines this with a metric cutpoint decomposition to obtain the $O(n^3)$ recognition and construction algorithm.","pith_inferences":["Editorial inference: the uniqueness result gives a concrete upper-bound test for the open problem on how large a graph must be to realize a finite metric: cactus metrics are realized by graphs with at most $|X|-2$ cycles, and the bound is sharp.","Editorial inference: a direct greedy compactification on arbitrary minimal cacti, without the cutpoint-decomposition preprocessing, may itself terminate in polynomial time; if so, the $O(n^3)$ pipeline could be simplified.","Editorial inference: the paper's discussion of graphs with block surplus $|E|-|V|+1\\le 2$ shows uniqueness can fail at the next level of generality, so the cactus class is a natural boundary; characterizing which surplus-2 metrics keep unique optimal realizations is a plausible next step."],"forward_implications":["Cactus metrics, like tree metrics, have a canonical minimal representative: the optimal realization is unique, so reconstruction algorithms need not break ties among equally good graphs.","The $O(n^3)$ recognition algorithm means cactus metrics can be tested and realized on finite metric spaces of moderate size; tree metrics remain the faster $O(n^2)$ special case.","Every optimal cactus realization has at most $|X|-2$ cycles and is planar, so the representation stays linear in size and easy to visualize.","Blockwise, an optimal cactus is assembled from trees and optimal cycles, so checking cactus-metric status reduces to checking that each block of the cutpoint decomposition is tree- or cycle-realizable."],"supporting_citations":[{"why":"supplies the tree-metric unique optimal realization theorem that Theorem 5 generalizes.","marker":"[8]"},{"why":"provides the block-decomposition optimality and uniqueness theorem and the cyclelike optimality criterion used in Lemma 4 and Theorem 5.","marker":"[12]"},{"why":"gives the metric cutpoint partition preprocessing that splits an arbitrary metric into single-block pieces.","marker":"[10]"},{"why":"underlies the cutpoint decomposition and bounds the number of blocks by $O(|X|)$.","marker":"[7]"},{"why":"observes that the cyclelike optimality condition alone does not characterize cyclelike metrics, motivating the verification step in Lemma 7.","marker":"[15]"},{"why":"provides related cycle-realization results that Lemma 7 builds on.","marker":"[2]"}],"fun_headline_variants":["Cactus metrics have exactly one optimal graph","Every cactus metric has a unique minimal realization","O(n³) algorithm finds unique cactus realization","Cactus metrics: recognized and realized in cubic time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of Theorem 5 relies on the unproved assertion that compactifying a slack vertex always yields a minimal $X$-cactus with strictly fewer slack vertices; if that local step ever fails, the uniqueness conclusion could be false.","fun_headline_variants_meta":{"raw":{"variants":["Cactus metrics have exactly one optimal graph","Every cactus metric has a unique minimal realization","O(n³) algorithm finds unique cactus realization","Cactus metrics: recognized and realized in cubic time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001435,"raw_usage":{"total_tokens":5764,"prompt_tokens":900,"completion_tokens":4864,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":516,"completion_tokens_details":{"reasoning_tokens":4806}},"tokens_in":516,"tokens_out":4864,"duration_ms":31453,"temperature":1.0,"reasoning_tokens":4806,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:11:33.655815+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Apply the compactification, as prescribed in the proof, to the 4-cycle with edge weights $1,2,1,1$ in cyclic order and the slack vertex $v_2$; the paper predicts the new graph still realizes the same metric and has fewer slack vertices. Computing all shortest-path distances before and after, and counting slack vertices, directly tests the local step on which Theorem 5 depends.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the tree-metric unique optimal realization theorem that Theorem 5 generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the block-decomposition optimality and uniqueness theorem and the cyclelike optimality criterion used in Lemma 4 and Theorem 5."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the metric cutpoint partition preprocessing that splits an arbitrary metric into single-block pieces."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"underlies the cutpoint decomposition and bounds the number of blocks by $O(|X|)$."},{"cited_title":"Sim˜ oes-Pereira, A note on distance matrices with unicyclic graph realizations, Discrete Mathematics 65(3) (1987) 277-287","cited_arxiv_id":null,"evidence_quote":"observes that the cyclelike optimality condition alone does not characterize cyclelike metrics, motivating the verification step in Lemma 7."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides related cycle-realization results that Lemma 7 builds on."}],"review_version":1}