Hierarchical $\mathcal{F}$-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

Michał Szyfelbein; Dariusz Dereniowski

cs.DSJul 14, 2026

Hierarchical $\mathcal{F}$ -Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

Authors: Michał Szyfelbein, Dariusz Dereniowski

Organizations: Gda´nsk University of Technology

Abstract

Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a graph belonging to a class $\mathcal{F}$ . We call this problem Hierarchical $\mathcal{F}$ -Clustering and we measure the quality of any solution using adapted Dasgupta's clustering objective. We study two natural choices of $\mathcal{F}$ : trees and graphs of bounded diameter. We present the first polynomial time $\mathcal{O}(\log n\cdot\log\log n)$ and $\mathcal{O}(\log n)$ -approximation algorithms for clustering into trees and bounded diameter graphs respectively. Our main technical contribution is a framework for approximating such problems based on linear programming. In fact, we characterize graphs classes $\mathcal{F}$ for which our approach can be applied and show that it includes both trees and bounded diameter graphs. However, our ideas are not limited to them and might be useful for other structures as well. Broadly speaking, our framework applies whenever the corresponding flat clustering problem, which we call $p_{\mathcal{F}}$ -Partitioning, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees. Intuitively, given a set of vertices called terminals, the problem is to find an edge set whose removal results in satisfying certain vertex-dependent structural predicate for each terminal. We then use these ingredients to build clustering trees with the aforementioned approximation guarantees. To complement these results, we show that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.

Explore similar work

Apr 26, 2026cs.DS

Characterizing Admissible Objective Functions for Hierarchical Clustering

Hierarchical clustering is a fundamental task in data analysis, but classical methods have long lacked a principled objective function. Dasgupta [STOC 2016] took an important step toward addressing this gap by proposing a well-motivated objective function for cluster trees. Cohen-Addad et al. [J. ACM 2019] subsequently introduced the notion of admissibility: an objective function is admissible if, whenever the input similarity matrix admits generating trees, its minimizers are precisely those generating trees. They also gave a necessary and sufficient condition for admissibility within a family of objective functions based on aggregate intercluster similarity. We refer to this family as sum-type objective functions. However, apart from Dasgupta's original objective function, no explicit admissible objective functions in this family were provided. In this paper, we study admissible objective functions for hierarchical clustering in two directions. For sum-type objective functions, we give a complete characterization when the scaling function is a symmetric polynomial of degree at most two, and we derive sufficient conditions for degree-three polynomials. We also show that the recursive sparsest cut algorithm achieves an O

(φ)

-approximation ratio for the admissible objective functions covered by our characterization, where

φ

is the approximation factor of the sparsest cut subroutine. We then introduce max-type objective functions, where cluster interaction is measured by maximum, rather than aggregate, intercluster similarity. For this class, we characterize which objective functions are admissible for arbitrary symmetric scaling functions and give a complete characterization when the scaling function is a symmetric polynomial of degree at most two.

Ryuki Tsukuba, Kazutoshi Ando

Image Clustering Objective Functions Maximum Independent Set Admissibility

Ask PDF

Jul 14, 2026cs.DS

Graph Partitioning with Demands: Generalized Conductance and its Applications

In this work, we study various graph partitioning problems under a general demand model. In each such task, we are given a graph

G=(V,E,c,w)

with a capacity function

c\colon E\to \mathbb{N}

and a demand function

w\colon V\times V\to \mathbb{N}

. Our main focus is the problem of finding a cut

(S, \bar{S})

minimizing the quantity

ψ_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}.

Here,

c( S, \bar{S} )

is the cost of edges between

S

and the complement of

S

\bar{S}

, and

w( S, V )=w( S )+w( S, \bar{S} )

is the sum of the internal demand within

S

w( S )

, and the demand between vertices of

S

and

\bar{S}

w( S, \bar{S} )

. We call

ψ_w( S )

the \emph{generalized conductance} of the cut

(S, \bar{S})

, and the task of minimizing

ψ_w( S )

the Generalized Conductance Problem. Our main contribution is an algorithm with an

\mathcal{O}(\log n)

-approximation guarantee for this objective. Our result is achieved via a two-way reduction: first to the well-known Generalized

k

-Multicut Problem, and then to a constrained variant of the classic Sparsest-Cut Problem, with an additional upper-bound constraint on the amount of demand that may be cut. Moreover, we show that the above procedure can be used to obtain an

\mathcal{O}(\log n)

-bicriteria approximation for Graph Partitioning with Demands, where the goal is to find a minimum-cost subset of edges

C

such that for every component

H

G\setminus C

w( H )\leq ρ\cdot w( V )

. This, in turn, yields an

\mathcal{O}(\log n)

-approximation for Hierarchical Clustering with Demands, the problem of finding a hierarchy of cuts that partitions the graph into increasingly refined clusters. For multiplicative demand functions, we improve these guarantees to

\mathcal{O}(\sqrt{\log n})

and for trees we get an

\mathcal{O}(1)

-approximation for all of our objectives.

Michał Szyfelbein, Dariusz Dereniowski

Maximum Independent Set Approximation Algorithms Partitioning

Ask PDF

Jun 17, 2026stat.ML

FOSC-X: An Extended Framework for Optimal Local Cuts and Non-Horizontal Cluster Selection from Clustering Hierarchies

Extracting a flat clustering solution from a hierarchy is a common task in practical cluster analysis and can be formulated as an optimisation problem. Existing approaches focus on finding a single optimal solution. We introduce FOSC-X, a framework for extracting the top-M globally optimal flat clusterings from local, non-horizontal cuts of a hierarchical cluster tree, while optionally enforcing constraints on the number of clusters. This enables automatic identification of multiple high-quality alternative clusterings that capture different aspects of the hierarchical structure. Without constraints, the top-M problem can be solved in polynomial time using dynamic programming, exploiting the property that locally optimal partial candidates within subtrees can be combined to form globally optimal solutions while automatically determining the number of clusters. However, this can lead to solutions with numbers of clusters that are ultimately undesirable -- e.g., too large to be meaningful or practically analysed within a particular application domain. Imposing cluster-count constraints breaks the optimality property underlying the unconstrained dynamic programming approach, since locally optimal partial candidates may no longer combine into feasible globally optimal solutions. FOSC-X addresses this challenge through a dynamic programming strategy that maintains compact sets of feasible candidates using lower and upper feasibility bounds while pruning infeasible or dominated combinations. The resulting method guarantees optimal rankings of the top-M solutions with linear-time complexity in the number of cluster nodes and dataset size, both with and without cluster-count constraints. Experiments show that FOSC-X efficiently reveals alternative clustering structures overlooked by single-solution extraction methods.

Connor Simpson, Ricardo J. G. B. Campello

Image Clustering Maximum Independent Set Oscillatory Dynamics

Ask PDF