Recognizing and realizing cactus metrics

Katharina T. Huber; Momoko Hayamizu; Vincent Moulton; Yukihiro Murakami

REVIEW 2 major objections 4 minor 17 references

Recognizing and realizing cactus metrics

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every cactus metric has a unique optimal realization, and there is a cubic-time algorithm to recognize it and build that realization.

desk verdict 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. read the letter →

arxiv 1908.01524 v2 pith:NGS3DW5I submitted 2019-08-05 math.CO cs.DM

Momoko Hayamizu , Katharina T. Huber , Vincent Moulton , Yukihiro Murakami This is my paper · ORCID

classification math.COcs.DM MSC 05C0505C1292B10

keywords cactusmetricX-cactusrealizationoptimalphylogeneticnetworkcyclelikecutpointdecompositionunique

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The 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.

But 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.

There 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.

The citation pattern looks fair; prior work by Hakimi–Yau, Imrich et al., and Hertz–Varone is used appropriately, and there is no circularity.

Bottom 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.

Referee Report

2 major / 4 minor

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.

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 (2)

[Section 4, Lemma 7 and Theorem 8] 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 3, proof of Theorem 5] 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.

minor comments (4)

[Section 3, Proposition 6] 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 4, Lemma 7] 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.
[Figure 2] 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.
[Introduction and references] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's central results are derived from external theorems and metric axioms, not from fitted parameters or self-referential definitions.

full rationale

The paper's central claim, Theorem 5, is that every cactus metric has a unique optimal realization. The proof invokes Theorem 1 (Imrich, Simoes-Pereira, Zamfirescu), Theorem 2 (Hakimi-Yau), and Theorem 3 (Imrich et al.) as external results, and the compactification argument is a constructive operation on graphs, not a quantity fitted from data. The concept 'cactus metric' is said to have been first introduced in reference [9], a self-citation by one of the authors, but this citation is only used to attribute the naming of the concept and is not load-bearing for the uniqueness theorem or the recognition algorithm. The algorithm in Lemma 7 and Theorem 8 checks minimality and uses the characterization in Theorem 3; although the correctness of Lemma 7 may be questionable for other reasons, that is a mathematical correctness risk, not circular reasoning. There are no fitted parameters, no predictions derived from the same data, and no uniqueness theorem imported solely from the authors' prior work. The unproved assertion that compactification strictly reduces the number of slack vertices is a gap in proof detail, but it is not equivalent to assuming the conclusion. Therefore the derivation chain is self-contained with respect to the named external theorems and the paper's own construction, and no circular step is exhibited.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper's central claims rest on several cited theorems from the metric realization literature and on two unproved assertions inside the proof of Theorem 5. No free parameters or invented entities are introduced.

assumptions (6)

standard math Every finite metric space has at least one optimal realization.
Invoked via citation [12, Theorem 2.2] to ensure the setting is nonempty; not proved in this paper.
standard math Block composition theorem: if each block is an optimal and unique realization of its induced metric, then the whole graph is optimal and unique.
Used as Theorem 1 in the proof of Theorem 5; cited from [12, Theorem 5.9].
standard math Cyclelike optimality criterion: a minimal cycle realization is optimal iff it has no slack vertex.
Used as Theorem 3/Lemma 4; cited from [12, Theorem 4.4].
domain assumption Hertz-Varone metric cutpoint decomposition produces blocks (Mi, di) such that any optimal realization of each block consists of a single block, can be glued together to form an optimal realization of (X,d), and can be computed in O(|X|^3) time.
Central to Theorem 8; correctness and runtime are cited from [10] and [7], not proved or reproduced here.
ad hoc to paper In a minimal X-cactus realization, every 3-cycle can be replaced by a tree without changing the realized metric or minimality.
Stated in the proof of Theorem 5 with no proof; if false, the reduction to cycles of length at least 4 fails.
ad hoc to paper The compactification operation of a slack vertex preserves the realized metric, preserves X-cactus structure and minimality, and strictly decreases the number of slack vertices.
The load-bearing step in the proof of Theorem 5; asserted with 'as can be easily verified' rather than proved.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Recognizing and realizing cactus metrics." pith.science (2026). https://pith.science/paper/NGS3DW5I

@misc{pith2026190801524,
  author       = {Pith},
  title        = {Pith review of: Recognizing and realizing cactus metrics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NGS3DW5I}},
  note         = {Machine review of arXiv:1908.01524}
}

abstract

The problem of realizing finite metric spaces in terms of weighted graphs has many applications. For example, the mathematical and computational properties of metrics that can be realized by trees have been well-studied and such research has laid the foundation of the reconstruction of phylogenetic trees from evolutionary distances. However, as trees may be too restrictive to accurately represent real-world data or phenomena, it is important to understand the relationship between more general graphs and distances. In this paper, we introduce a new type of metric called a cactus metric, that is, a metric that can be realized by a cactus graph. We show that, just as with tree metrics, a cactus metric has a unique optimal realization. In addition, we describe an algorithm that can recognize whether or not a metric is a cactus metric and, if so, compute its optimal realization in $O(n^3)$ time, where $n$ is the number of points in the space.

Figures

Figures reproduced from arXiv: 1908.01524 by the authors.

**Figure 1.** Note that cacti have some nice properties in common with trees. For instance, every cactus is planar and the number of vertices in an X-cactus is O(|X|) as with X-trees, which means that cactus metrics are easy to visualize. In particular, they provide a special case of an open problem in discrete geometry from Matouˇsek [13]. Besides these observations, in this paper we prove that, just as with tree metrics, any c… view at source ↗

**Figure 2.** An illustration of compactification that is described in the proof of Theorem 5, where we highlight each slack vertex [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

I.Alth¨ ofer, On optimal realizations of ﬁnite metric spaces by graphs, Discrete and Computational Geome- try 3(1) (1988) 103-122

work page 1988
[2]

A.Baldisserri, R.Elena, Distance matrices of some positive-weighted graphs, Australian Journal of Com- binatorics 70(2) (2018) 185-201

work page 2018
[3]

H.-J.Bandelt, Recognition of tree metrics, SIAM Jour- nal on Discrete Mathematics 3(1) (1990) 1-6

work page 1990
[4]

V.Batagelj, T.Pisanski, J.M.Sim˜ oes-Pereira, An algo- rithm for tree-realizability of distance matrices, Interna- tional Journal of Computer Mathematics 34(3-4) (1990) 171-176

work page 1990
[5]

J.C.Culberson, P.Rudnicki, A fast algorithm for con- structing trees from distance matrices, Information Pro- cessing Letters 30(4) (1989) 215-220

work page 1989
[6]

A.Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Advances in Mathematics 53(3) (1984) 321-402

work page 1984
[7]

A.Dress, K.T.Huber, J.Koolen, V.Moulton, A.Spillner, An algorithm for computing cutpoints in ﬁnite metric spaces, Journal of Classiﬁcation 27(2) (2010) 158-172

work page 2010
[8]

S.L.Hakimi, S.S.Yau, Distance matrix of a graph and its realizability, Quarterly of Applied Mathematics 22(4) (1965) 305-317

work page 1965

Show all 17 references

[9]

https://cdn.auckland.ac.nz/assets/compevol/events/ documents/Waiheke2017Programme.pdf

M.Hayamizu, X-cactus trees and cactus tree metrics, The 21st New Zealand Phylogenomics Meeting (Waiheke 2017), 12-17 February 2017. https://cdn.auckland.ac.nz/assets/compevol/events/ documents/Waiheke2017Programme.pdf

2017
[10]

A.Hertz, S.Varone, The metric cutpoint partition prob- lem, Journal of Classiﬁcation 25(2) (2008) 159-175

2008
[11]

D.H.Huson, R.Rupp, C.Scornavacca, Phylogenetic net- works: concepts, algorithms and applications, Cam- bridge University Press, 2010

2010
[12]

W.Imrich, J.M.Simoes-Pereira, C.M.Zamﬁrescu, On optimal embeddings of metrics in graphs, Journal of Combinatorial Theory, Series B 36(1) (1984) 1-15

1984
[13]

J.Matouˇ sek, 2.7 How large graph?, Open prob- lems on embeddings of ﬁnite metric spaces Workshop on discrete metric spaces and their algorithmic applications, 2002, available at http://kam.mﬀ.cuni.cz/∼matousek/metrop.ps

2002
[14]

C.Semple, M.Steel, Phylogenetics, Oxford University Press, 2003

2003
[15]

Sim˜ oes-Pereira, A note on distance matrices with unicyclic graph realizations, Discrete Mathematics 65(3) (1987) 277-287

J.M.S. Sim˜ oes-Pereira, A note on distance matrices with unicyclic graph realizations, Discrete Mathematics 65(3) (1987) 277-287

1987
[16]

Sim˜ oes-Pereira, C.M

J.M.S. Sim˜ oes-Pereira, C.M. Zamﬁrescu, Submatrices of non-tree-realizable distance matrices, Linear Algebra and its Applications 44 (1982) 1-17

1982
[17]

P.Winkler, The complexity of metric realization, SIAM Journal on Discrete Mathematics, 1(4) (1988) 552-559. 7

1988

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

I.Alth¨ ofer, On optimal realizations of ﬁnite metric spaces by graphs, Discrete and Computational Geome- try 3(1) (1988) 103-122

work page 1988

[2] [2]

A.Baldisserri, R.Elena, Distance matrices of some positive-weighted graphs, Australian Journal of Com- binatorics 70(2) (2018) 185-201

work page 2018

[3] [3]

H.-J.Bandelt, Recognition of tree metrics, SIAM Jour- nal on Discrete Mathematics 3(1) (1990) 1-6

work page 1990

[4] [4]

V.Batagelj, T.Pisanski, J.M.Sim˜ oes-Pereira, An algo- rithm for tree-realizability of distance matrices, Interna- tional Journal of Computer Mathematics 34(3-4) (1990) 171-176

work page 1990

[5] [5]

J.C.Culberson, P.Rudnicki, A fast algorithm for con- structing trees from distance matrices, Information Pro- cessing Letters 30(4) (1989) 215-220

work page 1989

[6] [6]

A.Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Advances in Mathematics 53(3) (1984) 321-402

work page 1984

[7] [7]

A.Dress, K.T.Huber, J.Koolen, V.Moulton, A.Spillner, An algorithm for computing cutpoints in ﬁnite metric spaces, Journal of Classiﬁcation 27(2) (2010) 158-172

work page 2010

[8] [8]

S.L.Hakimi, S.S.Yau, Distance matrix of a graph and its realizability, Quarterly of Applied Mathematics 22(4) (1965) 305-317

work page 1965