arxiv: 2605.03431 · v1 · submitted 2026-05-05 · 💻 cs.DS

Recognition: unknown

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning

Chao Xu, Mingdong Yang

Pith reviewed 2026-05-07 14:17 UTC · model grok-4.3

classification 💻 cs.DS

keywords cardinality-constrained diameter partitioningmaximum spanning treebottleneck 2-coloringtree dynamic programmingoptimal algorithmquery lower bound

0 comments

The pith

An O(n²) algorithm finds the optimal diameter-minimizing partition into two classes of any prescribed sizes, with a matching lower bound in the pairwise-query model.

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

The paper shows how to partition n items into two groups of given sizes so that the larger group diameter is as small as possible. It produces the optimum for every possible size pair in a single quadratic-time pass. The method improves an earlier O(n² log n) algorithm and is optimal when only pairwise weights can be examined. A reader would care because many clustering, facility-location, and network-design tasks reduce to finding low-diameter balanced divisions, and simultaneous computation for all sizes removes the need to rerun the procedure repeatedly.

Core claim

We give an O(n²) algorithm and a matching Ω(n²) lower bound if we can only query the weight between two elements. The algorithm computes the optimum for every cardinality simultaneously, improving Avis's O(n² log n). The reduction is to a bottleneck 2-coloring problem on the maximum spanning tree, solved by a standard tree DP. For a single cardinality with Euclidean weights, we obtain a subquadratic time algorithm in any fixed dimension.

What carries the argument

Reduction of the diameter-partitioning task to bottleneck 2-coloring on the maximum spanning tree, solved via tree dynamic programming.

If this is right

The optima for all cardinalities are available after one O(n²) computation.
No faster algorithm exists in the pairwise-query model.
A subquadratic algorithm exists for any single fixed cardinality under Euclidean distances in constant dimension.
The same tree-DP structure yields the optimum diameter partition without separate runs per size.

Where Pith is reading between the lines

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

The approach could be tested for extension to partitions into three or more classes if analogous bottleneck colorings on trees can be defined.
It may support online settings where new items arrive and all prior optima must be maintained efficiently.
The lower-bound argument suggests that any practical implementation must examine a quadratic number of pairs in the worst case.

Load-bearing premise

The reduction to bottleneck 2-coloring on the maximum spanning tree correctly captures the diameter of the optimal partition for any cardinality.

What would settle it

A concrete point set in which the minimum achievable maximum diameter for some cardinality differs from the value returned by the tree-DP solution on its maximum spanning tree.

read the original abstract

Cardinality-constrained diameter partitioning asks for a partition of $n$ items into two classes of prescribed sizes that minimizes the larger of the two class diameters. We give an $O(n^2)$ algorithm and a matching $\Omega(n^2)$ lower bound if we can only query the weight between two elements. The algorithm computes the optimum for every cardinality simultaneously, improving Avis's $O(n^2\log n)$. The reduction is to a bottleneck 2-coloring problem on the maximum spanning tree, solved by a standard tree DP. For a single cardinality with Euclidean weights, we obtain a subquadratic time algorithm in any fixed dimension.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean O(n²) algorithm for cardinality-constrained diameter partitioning that handles every split size at once, plus a matching lower bound.

read the letter

The main takeaway is that this work improves the time bound for cardinality-constrained diameter partitioning from O(n² log n) to O(n²) while computing the optimum for every cardinality in a single run, and it adds a matching Ω(n²) lower bound in the pairwise query model. That simultaneous computation for all k is the practical win on top of the asymptotic improvement over Avis's result. The method reduces the problem to bottleneck 2-coloring on the maximum spanning tree and solves it with tree DP, which is a standard and efficient move for these bottleneck-style objectives. For Euclidean weights in fixed dimension it even claims a subquadratic algorithm for one fixed cardinality. The approach earns credit for being direct and for showing the lower bound under the natural query assumption. The reduction looks plausible because maximum spanning trees preserve the relevant bottleneck information between pairs, and the DP can then enumerate the feasible colorings with size constraints without extra logarithmic factors. No circular reasoning appears in the high-level description, and the claims line up with known techniques for tree-based bottleneck problems. The main soft spot is the exact equivalence in the reduction: whether the minimum achievable max-diameter for a given cardinality truly equals the minimum bottleneck value from the tree 2-coloring for arbitrary weights. If the diameter is strictly the maximum direct pairwise weight inside each part, the tree paths must correctly capture when a high-weight pair ends up in the same class; the paper presumably proves both directions, but that step is load-bearing and worth verifying for edge cases like non-metric weights. Nothing else looks broken. This is a paper for people working on exact algorithms for graph partitioning, clustering, or combinatorial optimization with size constraints. A reader who needs an optimal solution for this specific problem or who wants to adapt the tree-DP technique to similar bottleneck objectives will get direct value. It deserves a serious referee because the improvement is concrete, the lower bound is tight, and the method is simple enough to check. I would send it to peer review.

Referee Report

1 major / 1 minor

Summary. The paper claims an O(n²) algorithm for cardinality-constrained diameter partitioning that computes the optimum for every cardinality k simultaneously by reducing the problem to bottleneck 2-coloring on the maximum spanning tree (solved via tree DP), along with a matching Ω(n²) lower bound in the pairwise query model. It improves on Avis's O(n² log n) bound and gives a subquadratic algorithm for Euclidean weights in fixed dimension.

Significance. If the reduction is correct, the result is significant: it achieves optimal time, provides all cardinalities at once, and matches the lower bound. The simultaneous computation and tree-DP approach would be a clean technical contribution over prior work.

major comments (1)

[reduction to bottleneck 2-coloring on the maximum spanning tree] The reduction (described after the abstract and in the algorithm section): the claimed equivalence between the minimum achievable max-diameter for a given cardinality and the minimum bottleneck value from 2-coloring the maximum spanning tree (such that no monochromatic path/component exceeds the bottleneck) is load-bearing. For arbitrary weights, the threshold graph G_{>t} may contain odd cycles from non-tree edges even when the max-ST forest for edges >t is bipartite; the tree DP would then return an incorrect (too-low) value. The proof must explicitly show why extra high-weight edges do not create additional conflicts or why the max-ST suffices to capture the exact diameter for every k.

minor comments (1)

[Abstract] The abstract states the complexity results clearly but does not cite Avis's work; adding the reference would improve context.

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The paper derives an O(n²) algorithm via reduction of cardinality-constrained diameter partitioning to bottleneck 2-coloring on the maximum spanning tree, solved by standard tree DP, plus a matching query lower bound. No step equates a claimed result to its own inputs by definition, renames a fitted quantity as a prediction, or relies on load-bearing self-citation whose cited result is itself unverified. The reduction and DP are presented as independent of the target optimum; the lower bound follows from the pairwise-query model without circularity. The derivation is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the correctness of reducing diameter partitioning to bottleneck 2-coloring on the MST and solving it via tree DP. No free parameters or invented entities are introduced.

axioms (2)

domain assumption Pairwise weights are available via queries and form a complete graph
Required for both the algorithm and the Omega(n^2) lower bound in the query model.
domain assumption The maximum spanning tree preserves the bottleneck diameter properties needed for optimal partitions
This is the key step in the reduction described in the abstract.

pith-pipeline@v0.9.0 · 5395 in / 1232 out tokens · 79514 ms · 2026-05-07T14:17:36.656545+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 12 canonical work pages · 1 internal anchor

[1]

Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl

Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean minimum spanning trees and bichromatic closest pairs.Discrete & Computational Geometry, 6(3):407–422, 1991.doi:10.1007/BF02574698. 4

work page doi:10.1007/bf02574698 1991
[2]

Agarwal, Ji ˇrí Matoušek, and Subhash Suri

Pankaj K. Agarwal, Ji ˇrí Matoušek, and Subhash Suri. Farthest neighbors, maximum span- ning trees and related problems in higher dimensions.Computational Geometry: Theory and Applications, 1(4):189–201, 1992.doi:10.1016/0925-7721(92)90001-9

work page doi:10.1016/0925-7721(92)90001-9 1992
[3]

Clustering algorithms based on minimum and maximum spanning trees

Tetsuo Asano, Binay Bhattacharya, Mark Keil, and Frances Yao. Clustering algorithms based on minimum and maximum spanning trees. InProceedings of the Fourth Annual Symposium on Computational Geometry (SoCG), pages 252–257, 1988.doi:10.1145/73393.73419

work page doi:10.1145/73393.73419 1988
[4]

Diameter partitioning.Discrete & Computational Geometry, 1(3):265–276, 1986

David Avis. Diameter partitioning.Discrete & Computational Geometry, 1(3):265–276, 1986. doi:10.1007/BF02187699

work page doi:10.1007/bf02187699 1986
[5]

Complexity measures and decision tree complexity: A survey.Theoretical Computer Science, 288(1):21–43, 2002

Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: A survey.Theoretical Computer Science, 288(1):21–43, 2002. doi:10.1016/S0304-3975(01) 00144-X

work page doi:10.1016/s0304-3975(01 2002
[6]

A polynomial algorithm for balanced clustering via graph partitioning, 2018

Luis Evaristo Caraballo, José Miguel Díaz-Báñez, and Nadine Kroher. A polynomial algorithm for balanced clustering via graph partitioning, 2018. URL: https://arxiv.org/abs/1801.03347, arXiv:1801.03347

work page arXiv 2018
[7]

Cormen, Charles E

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms. MIT Press, 3 edition, 2009

2009
[8]

The maximum dispersion problem

Elena Fernández, Jörg Kalcsics, and Stefan Nickel. The maximum dispersion problem.Omega, 41(4):721–730, 2013.doi:10.1016/j.omega.2012.09.005

work page doi:10.1016/j.omega.2012.09.005 2013
[9]

Faster pseudopolynomial time algorithms for subset sum

Konstantinos Koiliaris and Chao Xu. Faster pseudopolynomial time algorithms for subset sum. ACM Transactions on Algorithms, 15(3), 2019. URL: https://chaoxu.prof/files/papers/subset- sum-journal.pdf,doi:10.1145/3329863

work page doi:10.1145/3329863 2019
[10]

Computing euclidean maxi- mum spanning trees.Algorithmica, 5(3):407–419, 1990.doi:10.1007/BF01840371

Clyde Monma, Michael Paterson, Subhash Suri, and Frances Yao. Computing euclidean maxi- mum spanning trees.Algorithmica, 5(3):407–419, 1990.doi:10.1007/BF01840371

work page doi:10.1007/bf01840371 1990
[11]

Monma and Subhash Suri

Clyde L. Monma and Subhash Suri. Partitioning points and graphs to minimize the maximum or the sum of diameters. In Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schwenk, editors, Graph Theory, Combinatorics, and Applications, volume 2. Wiley, 1991. Conference held at Western Michigan University , June 1988

1991
[12]

Springer (1985)

Franco P . Preparata and Michael Ian Shamos.Computational Geometry: An Introduction. Springer, 1985.doi:10.1007/978-1-4612-1098-6

work page doi:10.1007/978-1-4612-1098-6 1985
[13]

Robert C. Prim. Shortest connection networks and some generalizations.Bell System Technical Journal, 36(6):1389–1401, 1957.doi:10.1002/j.1538-7305.1957.tb01515.x

work page doi:10.1002/j.1538-7305.1957.tb01515.x 1957
[14]

Nguyen Khoa Tran, Lin Mu, Martin Papenberg, and Gunnar W . Klau. Coloring for dispersion: A polynomial-time algorithm for cardinality-constrained 2-anticlustering, 2026. URL: https: //arxiv.org/pdf/2604.24285,arXiv:2604.24285. 5

work page internal anchor Pith review Pith/arXiv arXiv 2026