# Dasgupta's Hierarchical Clustering Objective: Geometry and the Price of the Cardinality Constraint

Preprint · Peiyuan Sun

- Archive id: arxiv:2609.07205
- Published: 2026-09-07
- arXiv: https://arxiv.org/abs/2609.07205
- Source URL: https://arxiv.org/abs/2609.07205
- PDF: https://arxiv.org/pdf/2609.07205
- Provenance: arxiv

## Abstract

The cost of a hierarchical clustering can be represented by an ultrametric whose lowest-common-ancestor labels are cluster cardinalities. We relate this known representation to the shortest-path geometry of a similarity graph. For a connected support graph $G$, let $d\_G$ be its unit-length shortest-path metric and let the edge weights enter only the objective. We prove that the shifted Dasgupta optimum is exactly the minimum edge-weighted cost of a cardinality-realizable ultrametric that dominates $d\_G$. Connectedification lemmas put this problem and its freely labeled dominating-ultrametric relaxation on the same class of connected binary hierarchies, labeled respectively by cardinality and graph diameter. As a sharp baseline, we determine the exact worst-case price of cardinality realizability: on every $n$-vertex instance the ratio of the two optima is at most $(2n-1)/3$, with equality on the unweighted complete graph; the sharp factor for the standard unshifted objective is $2(n+1)/3$. Our principal structural result bounds this gap by a hereditary weighted fragmentation profile defined through connected balanced cuts. Uniform local control gives an $O(\\log n)$ gap, polynomial decay gives a constant gap, and the logarithmic order is tight even for unweighted trees of maximum degree $3$. On locally regular bounded-degree trees, the hierarchy can be constructed in $O(n\\log n)$ time. An energy decomposition and a geometric density bound provide supporting instance-sensitive estimates. Thus the cardinality label has an unavoidable linear worst case but admits substantially smaller bounds on natural sparse graph classes.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.