Pith. sign in

REVIEW 2 major objections 3 minor 18 references

The paper gives a deterministic exact algorithm for the minimum-number-of-Steiner-points bounded-edge-length tree problem that runs in n^{O(n)} time, independent of the optimum number k of Steiner points.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review

2026-08-05 00:14 UTC pith:3J7QY3EP

load-bearing objection A genuinely new exact algorithm for STP-MSPBEL, but the n^{O(n)} claim is only proven in a unit-cost model that ignores coefficient growth; still worth a careful referee. the 2 major comments →

arxiv 2608.00795 v1 pith:3J7QY3EP submitted 2026-08-01 cs.CG cs.DS

Exact Algorithms for Minimum Steiner Point Trees

Eungyu Woo , Donghoon Shin This is my paper
classification cs.CG cs.DS MSC 05C0568Q2568U05
keywords Steiner treeminimum Steiner pointsbounded edge lengthexact algorithmfull Steiner topologyinteger convex feasibilitybottleneck Steiner treeL_p metric
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper seeks to establish that the bounded-edge-length Steiner tree problem with minimum number of Steiner points (STP-MSPBEL) is exactly solvable in time n^{O(n)} for n terminals in the plane, in any fixed L_p metric with rational p or infinity—and, crucially, that this time bound does not involve the optimal number k of Steiner points. Since a long gap between two terminals forces an arbitrarily long chain of subdivision points, k can be much larger than n, so the usual parameterized running times are not the natural measure. The paper proves that every optimum can be lifted to a full Steiner topology: an abstract tree with n labeled leaf terminals and n-2 degree-three branch points, with each edge assigned an integer number q_e of equal length-R segments. For a fixed topology, the feasible segment-count vectors are exactly the integer points of a convex set in O(n) dimensions, and a continuous relaxation leaves only 2n-3 candidate objective values to test. Exact semialgebraic optimization plus a Lenstra-style flatness recursion decides each test, giving the n^{O(n)} bound, and combining with a parameterized bottleneck algorithm gives the value bound min{n^{O(n)}, k^{O(k)}n^{O(1)}}.

Core claim

The paper's central claim is that STP-MSPBEL admits a deterministic exact algorithm computing an optimal implicit representation—a full Steiner topology H, exact branch coordinates x, and integer segment counts q—in n^{O(n)} time, independent of the optimal Steiner point count k. The reduction: any optimum tree can be pruned, straightened, and split into a full Steiner topology whose n-2 degree-three vertices capture the branching and whose edges carry integer counts of length-R segments; the Steiner count is 1 - n + sum_e q_e. For each topology, feasible q are exactly the integer points of a convex projection C_H in O(n) dimensions, and a continuous relaxation pins the integer optimum to at

What carries the argument

The central object is the full Steiner topology: an abstract tree whose leaves are exactly the n labeled terminals and whose n-2 other vertices are unlabeled and have degree three. Around it sits the beading identity of Brazil, Ras, and Thomas: every edge can be divided into q_e equal segments of length at most R, so the total number of Steiner points becomes sum_e q_e - n + 1. The mechanism that carries the argument is the convex segment-count set C_H, whose integer points are precisely the feasible segment-count vectors for a fixed topology. Its continuous optimum lambda_H leaves only 2n-3 candidate integer objective values, and compact threshold bodies K_{H,M} = C_H cap {1^T q <= M + 1/2}

Load-bearing premise

The n^{O(n)} bound is proved in the paper's computation model where coefficient bit lengths and coefficient growth are not charged; if a standard bit-complexity accounting is used, the stated k-independence would need restating.

What would settle it

Check the crux on a small instance by brute force: take n=4 terminals in the Euclidean plane, R=1, coordinates chosen so a continuous optimum is irrational; compute lambda_H for one full topology by the paper's semialgebraic routines, then enumerate every integer vector q in the 5-dimensional box [0, ceil(diam(B))]^5 with sum between ceil(lambda_H) and ceil(lambda_H)+5, testing membership in C_H with Theorem 2. If the first feasible q has sum greater than ceil(lambda_H)+2n-4, the central reduction fails; if it matches, the concluding lemma is corroborated on that instance.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • An optimal tree can be represented without enumerating its subdivision points: a topology plus O(n) integer counts is enough, and expanding it to full geometry is linear in the output size.
  • The running time n^{O(n)} is free of k, so instances with enormous relay chains remain exactly solvable in the paper's computation model whenever n is modest.
  • For the dual bottleneck problem, the same full-topology approach computes the optimum bottleneck value beta_j(P) with a budget of j Steiner points in (n+j)^{O(n)} time.
  • When k is small, the k^{O(k)} n^{O(1)} parameterized algorithm dominates; when n is small, the n^{O(n)} algorithm dominates; taking the minimum of the two bounds the exact value.
  • For n=3 the problem reduces to a three-terminal branching minimization, matching the previously studied special case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • I would expect the segment-count and convex-projection reduction to transfer to Steiner trees in higher dimensions or with degree bounds, because the argument uses the shape of the objective rather than planarity; the paper itself only proves the planar case.
  • The 2n-3 candidate window is likely loose in practice; a sharper coupling between the continuous optimum and the integer optimum could shrink the constant in the n^{O(n)} exponent, though the paper does not pursue that.
  • The computation model hides coefficient growth; under a standard bit-complexity accounting the theorems would probably gain extra factors in coefficient bit size, which matters for any numerical implementation.
  • The bottleneck equivalence suggests that minimum relay count and minimum maximum edge length are two views of one optimization; a practical route could binary-search R with the parameterized algorithm instead of enumerating all topologies.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper studies STP-MSPBEL in the plane for L_p metrics with p in Q_{>=1} union {infinity}. It introduces an 'implicit representation' consisting of a full Steiner topology, exact branch coordinates, and per-edge segment counts, and proves that minimizing the number of Steiner points is equivalent to minimizing a sum of ceiling-type edge counts over all full Steiner topologies. For each topology, the feasible segment-count vectors form a convex set C_H, and a continuous relaxation gives a window of only 2n-3 candidate integer objective values. The paper then uses exact semialgebraic routines and a Lenstra-type lattice recursion to decide integer feasibility of threshold bodies in n^{O(n)} arithmetic operations, independent of the optimal Steiner count k. A separate parameterized argument (via Bandyapadhyay et al.) yields a hybrid bound min{n^{O(n)}, k^{O(k)} n^{O(1)}} for the value. The main technical apparatus is an Appendix A integer-feasibility theorem built on flatness, ellipsoid rounding, and shortest-vector computations.

Significance. If the derivation is correct, this is a significant theoretical contribution: it decouples the branch structure from the (possibly huge) number of subdivision points and gives the first exact algorithm whose arithmetic-operation count is independent of k, improving on the purely k-parameterized view. The paper re-derives the beading/full-representation facts rather than citing them opaquely, and the convex rounding Lemma 12 is elegant. The main caveat is that the stated bound is in the paper's own unit-cost model of Section 2.2, which does not charge coefficient bit growth; as a standard bit-complexity statement the result is not established. The appendix gives a substantial self-contained proof of the integer feasibility engine, though several steps are compressed.

major comments (2)
  1. [Section 2.2, Theorems 17/18/22] The computation model in Section 2.2 explicitly does not charge coefficient bit lengths or coefficient growth; this is nonstandard for a claimed 'time' bound. Theorems 17, 18, and 22 state running times n^{O(n)} without repeating this qualification. The headline 'independent of the optimum number of Steiner points' is therefore only an arithmetic-complexity statement, not a Turing/bit-complexity bound. The authors should state the model in every such theorem and discuss whether a bit-complexity version can be extracted (e.g., by bounding algebraic coefficient sizes in the BPR routines). This is load-bearing for the central claim.
  2. [Appendix A, Lemmas 23-25] The proof of Theorem 4 depends on a chain of technical lemmas whose statements are plausible but whose proofs are only sketched. In particular, Lemma 23's rounding denominator, the determinant estimate |det B| <= 2^r L^{r-1} epsilon, and the Minkowski/shortest-vector step are not fully expanded, and Lemma 24's inner-ball/outer-ball constants are asserted after rounding. Since Theorem 4 is the engine for the fixed-topology feasibility tests, the reader needs enough detail to verify the r^{O(r)} A bound and the preservation of outer-radius data under all recursive transformations. Please expand these proofs or give precise theorem/lemma numbers from [2,11,17] for each step.
minor comments (3)
  1. [Section 3.6, Theorem 22 proof] The proof states the two bounds and the value is computed in their minimum, but does not explain how a single deterministic algorithm achieves the min without knowing k in advance. A sentence on interleaving the two algorithms or using a timeout window would clarify the claimed bound.
  2. [Section 3.3, Lemma 12] The upper bound proof writes 'mu_H <= lambda_H + |E(H)|' and then 'by integrality' obtains the window. This is correct, but the final inequality '<= ceil(lambda_H)+2n-4' would benefit from a one-line justification for non-integer lambda_H.
  3. [Throughout] Several typographical issues appear ('degreetwo', 'In particular, the problem is fixed-parameter tractable' referring to a cited theorem, and inconsistent use of math formatting). A careful proofread is recommended.

Circularity Check

0 steps flagged

No significant circularity: the load-bearing derivation is self-contained, with only a non-load-bearing self-citation and an external computation-model caveat.

full rationale

The paper's central claim is that STP-MSPBEL can be solved exactly in n^{O(n)} time independent of the optimum number k of Steiner points. Walking the derivation chain: Lemma 10 proves the equivalence k* = min_H (mu_H - n + 1) by re-proving the full-Steiner and beading facts rather than importing them as a black box. Lemma 11 reduces the fixed-topology optimization to integer points of a convex segment-count set, and Lemma 12 bounds the integer optimum to 2n-3 candidate values. The semialgebraic routine (Theorem 2) is cited to Basu, Pollack, and Roy, an external textbook; the convex integer feasibility theorem (Theorem 4) is proved in Appendix A via Lenstra's recursion, Dadush-Peikert-Vempala, and the external flatness theorem of Banaszczyk et al. and Rudelson. The hybrid bound in Theorem 22 invokes Bandyapadhyay et al. [3], an external fixed-parameter-tractable bottleneck algorithm. The only self-citation is [18] (co-author D. Shin), used in a remark for the n=3 branching problem; it is not load-bearing. No parameter is fitted to data, no prediction is defined in terms of its own input, and no uniqueness theorem is imported from the authors' prior work. The computation model of Section 2.2 says "Coefficient bit lengths and coefficient growth are not charged," so the n^{O(n)} and k-independence statements are proved in an exact-arithmetic arithmetic-operation model rather than a standard bit-complexity model. This is a meaningful caveat about the interpretation and generality of the claimed bound, but it is not a circularity: the theorem is still proved from stated assumptions and external mathematical results, and no equation reduces to itself by construction. Accordingly, the circularity score is 0.

Axiom & Free-Parameter Ledger

1 free parameters · 7 axioms · 1 invented entities

No instance-fitted parameters. The universal constants in Appendix A are absorbed by the asymptotic notation. The framework of [5] is re-derived; the FPT dual bound and the flatness machinery are external cited results. One representational device (implicit representation) is introduced and proven correct.

free parameters (1)
  • Universal constants in Appendix A (C_f, c_f, C', m, epsilon, L, N) = n/a (universal, not instance-fitted)
    Chosen in Appendix A to make the flatness recursion and rounding arguments work (e.g., epsilon=(16 r L)^(-r), phi(r)=C' r^m). They are not fitted to problem data and their exact values are absorbed by the r^{O(r)} and n^{O(n)} notation, so they do not change the asymptotic claim.
axioms (7)
  • standard math Nonsymmetric flatness theorem with width bound w_Z(C) <= C_f r^{4/3} log^{c_f}(2r) [2,17]
    Invoked in Appendix A.2 to guarantee a lattice point in the wide case after homothetic shrinking; constants inherited from cited results.
  • standard math Shortest vector in any well-centered norm is computable deterministically in 2^{O(r)} time and space (Dadush-Vempala, cited as Theorem 1.6 in [12])
    Used in Lemmas 23 and 25 to compute minimum-width directions and short lattice vectors; the paper relies on the cited theorem for the exact cost.
  • standard math Exact semialgebraic emptiness, point recovery, and optimization at cost (s*delta)^{O(N)} (Basu, Pollack and Roy [4, Theorems 13.22 and 14.16])
    Theorem 2; all lifting, projection, and witness recovery steps rest on these routines in the coefficient domain of Section 2.2.
  • standard math Minkowski's first theorem
    Used in Lemma 23 to show the flat ellipsoid contains a nonzero lattice vector of the transformed lattice.
  • domain assumption Bandyapadhyay et al. [3] solve Euclidean Bottleneck Steiner Tree in k^{O(k)} n^{O(1)} and state an L_p extension for p in Q_{>=1} union {infinity}
    Theorem 21; the hybrid min-bound of Theorem 22 and the abstract depend on this external result and its claimed L_p extension, which the present paper quotes without full restatement.
  • domain assumption Unit-cost arithmetic in a real closed field with coefficient growth uncharged (Section 2.2 computation model)
    Every complexity theorem in the paper is stated in this model; the k-independence claim does not transfer automatically to a bit-complexity model.
  • standard math Brazil, Ras and Thomas [5] beading identity and full Steiner representation, re-proved in Lemmas 5-7 and 10
    The paper gives short proofs of the needed forms rather than pure citation, so the foundation is independently verifiable.
invented entities (1)
  • Implicit representation (full Steiner topology, exact branch coordinates, segment counts) no independent evidence
    purpose: Encodes an optimal STP-MSPBEL solution without storing degree-two subdivision points, enabling running time independent of k
    This is a proof and data-structure artifact, not a physical hypothesis; its correctness is established by Theorems 16-18, so no external falsifiable handle applies.

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Exact Algorithms for Minimum Steiner Point Trees." pith.science (2026). https://pith.science/paper/3J7QY3EP

@misc{pith2026260800795,
  author       = {Pith},
  title        = {Pith review of: Exact Algorithms for Minimum Steiner Point Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3J7QY3EP}},
  note         = {Machine review of arXiv:2608.00795}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Given distinct terminals $P\subset R^2$ and $R>0$, the Steiner tree problem with minimum number of Steiner points and bounded edge length asks for a straight line tree spanning $P$, with every edge of length at most $R$, that minimizes the number of Steiner points. Length is measured in a fixed $L_p$ metric with $p\in Q_{\ge 1}\cup\{\infty\}$. The optimum $k$ is not bounded by $n$, even in two-terminal case. We give a deterministic exact algorithm that computes an optimal implicit representation in $n^{O(n)}$ time, independent of $k$, in the computation model of Section~\ref{subseccomputation}. The representation consists of a full Steiner topology, exact branch coordinates, and a segment count for each topology edge. Subdivision requires additional time $\Theta(n+k)$. For each full Steiner topology, the feasible segment count vectors are the integer points of a convex projection in $O(n)$ dimensions. A continuous relaxation restricts the integer optimum to $2n-3$ consecutive values. Exact semialgebraic routines and a flatness recursion in integral lattice coordinates decide these values. Together with the parameterized bottleneck algorithm of Bandyapadhyay et al., this gives the value bound $\min\{n^{O(n)}, k^{O(k)}n^{O(1)}\}$ for every fixed metric considered here.

Figures

Figures reproduced from arXiv: 2608.00795 by Donghoon Shin, Eungyu Woo.

Figure 1
Figure 1. Figure 1: The two operations behind a full Steiner representation. A degree four junction is split into degree three vertices joined by a zero length edge. Beading divides an edge into 𝑞𝑒 bounded length segments. Lemma 9. The number of full Steiner topologies on 𝑛 ≥ 3 labeled terminals is 𝐹𝑛 = (2𝑛−5)!! = (2𝑛−4)!∕(2𝑛−2(𝑛−2)!). PROOF. There is one full Steiner topology for 𝑛 = 3. Removing a prescribed terminal and sup… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 15 canonical work pages · 2 internal anchors

  1. [1]

    Exact algorithms for the bottleneck steiner tree problem

    Bae, S.W., Choi, S., Lee, C., ichi Tanigawa, S., 2011. Exact algorithms for the bottleneck steiner tree problem. Algorithmica 61, 924–948. doi:10.1007/s00453-011-9553-y

    work page doi:10.1007/s00453-011-9553-y 2011

  2. [2]

    The flatness theorem for nonsymmetric convex bodies via the local theory of banach spaces

    Banaszczyk, W., Litvak, A.E., Pajor, A., Szarek, S.J., 1999. The flatness theorem for nonsymmetric convex bodies via the local theory of banach spaces. Mathematics of Operations Research 24, 728–750. doi:10.1287/moor.24.3.728

    work page doi:10.1287/moor.24.3.728 1999

  3. [3]

    Euclidean bottleneck steiner tree is fixed-parameter tractable, in: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, pp

    Bandyapadhyay, S., Lochet, W., Lokshtanov, D., Saurabh, S., Xue, J., 2024. Euclidean bottleneck steiner tree is fixed-parameter tractable, in: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 699–711. doi:10.1137/1.9781611977912.27

    work page doi:10.1137/1.9781611977912.27 2024

  4. [4]

    Algorithms in Real Algebraic Geometry

    Basu, S., Pollack, R., Roy, M.F., 2006. Algorithms in Real Algebraic Geometry. volume 10 ofAlgorithms and Computation in Mathematics. 2 ed., Springer, Berlin, Heidelberg. doi:10.1007/3-540-33099-2

    doi:10.1007/3-540-33099-2 2006

  5. [5]

    Approximating minimum steiner point trees in minkowski planes

    Brazil, M., Ras, C.J., Thomas, D.A., 2010. Approximating minimum steiner point trees in minkowski planes. Networks 56, 244–254. doi:10.1002/net.20376

    work page doi:10.1002/net.20376 2010

  6. [6]

    Generalised𝑘-steiner tree problems in normed planes

    Brazil, M.N., Ras, C.J., Swanepoel, K.J., Thomas, D.A., 2015. Generalised𝑘-steiner tree problems in normed planes. Algorithmica 71, 66–86. doi:10.1007/s00453-013-9780-5

    work page doi:10.1007/s00453-013-9780-5 2015

  7. [7]

    Combination algorithms for steiner tree variants

    Călinescu, G., Wang, X., 2023. Combination algorithms for steiner tree variants. Algorithmica 85, 153–169. doi: 10.1007/ s00453-022-01009-8

    work page 2023

  8. [8]

    Approximations for steiner trees with minimum number of steiner points

    Chen, D., Du, D.Z., Hu, X.D., Lin, G.H., Wang, L., Xue, G., 2001. Approximations for steiner trees with minimum number of steiner points. Theoretical Computer Science 262, 83–99. doi:10.1016/S0304-3975(00)00182-1

    work page doi:10.1016/s0304-3975(00)00182-1 2001

  9. [9]

    Relay sensor placement in wireless sensor networks

    Cheng, X., Du, D.Z., Wang, L., Xu, B., 2008. Relay sensor placement in wireless sensor networks. Wireless Networks 14, 347–355. doi:10.1007/s11276-006-0724-8

    work page doi:10.1007/s11276-006-0724-8 2008

  10. [10]

    Approximating steiner trees and forests with minimum number of steiner points

    Cohen, N., Nutov, Z., 2018. Approximating steiner trees and forests with minimum number of steiner points. Journal of Computer and System Sciences 98, 53–64. doi:10.1016/j.jcss.2018.08.001

    work page doi:10.1016/j.jcss.2018.08.001 2018

  11. [11]

    Enumerative Lattice Algorithms in Any Norm via M-Ellipsoid Coverings

    Dadush, D., Peikert, C., Vempala, S., 2011. Enumerative lattice algorithms in any norm via M-ellipsoid coverings.arXiv:1011.5666. proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  12. [12]

    Near-Optimal Deterministic Algorithms for Volume Computation and Lattice Problems via M-Ellipsoids

    Dadush, D., Vempala, S.S., 2012. Near-optimal deterministic algorithms for volume computation and lattice problems via m-ellipsoids. arXiv:1201.5972

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  13. [13]

    Integer programming with a fixed number of variables

    Lenstra, Jr., H.W., 1983. Integer programming with a fixed number of variables. Mathematics of Operations Research 8, 538–548. doi:10.1287/moor.8.4.538

    doi:10.1287/moor.8.4.538 1983

  14. [14]

    Steiner tree problem with minimum number of steiner points and bounded edge-length

    Lin, G.H., Xue, G., 1999. Steiner tree problem with minimum number of steiner points and bounded edge-length. Information Processing Letters 69, 53–57. doi:10.1016/S0020-0190(98)00201-4

    work page doi:10.1016/s0020-0190(98)00201-4 1999

  15. [15]

    A note on the MST heuristic for bounded edge-length steiner trees with minimum number of steiner points

    Măndoiu, I.I., Zelikovsky, A.Z., 2000. A note on the MST heuristic for bounded edge-length steiner trees with minimum number of steiner points. Information Processing Letters 75, 165–167. doi:10.1016/S0020-0190(00)00095-8

    work page doi:10.1016/s0020-0190(00)00095-8 2000

  16. [16]

    Wireless network design via 3-decompositions

    Nutov, Z., Yaroshevitch, A., 2009. Wireless network design via 3-decompositions. Information Processing Letters 109, 1136–1140. doi:10.1016/j.ipl.2009.07.013

    work page doi:10.1016/j.ipl.2009.07.013 2009

  17. [17]

    Distances between non-symmetric convex bodies and the𝑀𝑀∗-estimate

    Rudelson, M., 2000. Distances between non-symmetric convex bodies and the𝑀𝑀∗-estimate. Positivity 4, 161–178. doi:10.1023/A: 1009842406728

    doi:10.1023/a: 2000

  18. [18]

    An efficient 3-approximation algorithm for the steiner tree problem with the minimum number of steiner points and bounded edge length

    Shin, D., Choi, S., 2023. An efficient 3-approximation algorithm for the steiner tree problem with the minimum number of steiner points and bounded edge length. PLOS ONE 18, e0294353. doi:10.1371/journal.pone.0294353. E. Woo and D. Shin:Preprint submitted to ElsevierPage 14 of 14

    work page doi:10.1371/journal.pone.0294353 2023

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.