💻 computer science

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

This paper introduces Hierarchical $\mathcal{F}$ -Clustering, a generalized framework that relaxes standard clustering halting conditions to stop when clusters belong to a specific class $\mathcal{F}$ , and presents the first polylogarithmic approximation algorithms for trees and bounded diameter graphs using a novel linear programming-based approach while proving their inapproximability within constant factors under the Small Set Expansion Hypothesis.

Original authors: Michał Szyfelbein, Dariusz Dereniowski

Published 2026-07-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Michał Szyfelbein, Dariusz Dereniowski

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are organizing a massive, chaotic library. You have thousands of books, and your goal is to sort them into a hierarchy. You start with the whole library, then split it into sections, then into shelves, then into individual stacks, until every single book is in its own tiny pile. This is the classic way computers "cluster" data: they keep chopping things up until everything is alone. But what if you stopped earlier? What if you decided that a whole shelf of books about "19th-century French poetry" was a perfect, final group, and you didn't need to split it down to single volumes? This is the question a new piece of research asks: Can we build these sorting trees efficiently when we allow the final groups to be small, tidy structures (like a tree or a compact circle) rather than just single items?

This work lives in the world of computer science, specifically in the realm of algorithms that organize data. The core idea relies on a method called "hierarchical clustering," which builds a family tree of groups. The quality of this tree is measured by a score that punishes you for cutting apart things that are very similar too early in the process. The researchers are asking: If we change the rules so the process stops when a group looks like a specific shape (like a tree or a group where everyone is close to everyone else), can we still find a good sorting plan quickly? They found that yes, we can, but only with a specific mathematical trick, and that finding a perfect plan is likely impossible for computers to do quickly.

The Great Data Sorting Game

Think of a dataset as a giant, messy party where everyone is holding hands with people they like. The strength of the hand-hold is how much they like each other. The goal of Hierarchical Clustering is to build a family tree of this party. You start with the whole crowd, then you cut some hand-holds to split the party into two smaller groups. Then you cut more hand-holds to split those groups further, and so on.

Usually, the game only ends when every single person is standing alone. But in this new study, the authors, Michał Szyfelbein and Dariusz Dereniowski, ask a fun "What if?" question: What if we stop the game early? What if we say, "Okay, this group of ten people is already a perfect little circle of friends, so we don't need to break them up anymore"? Or, "This group forms a nice tree shape, so let's leave it alone"? They call this Hierarchical F-Clustering, where "F" stands for the specific shape or rule you want your final groups to follow.

The researchers wanted to know two things:

Can we build these "stop-early" trees quickly and efficiently?
How close to the "perfect" tree can we get without spending forever on the calculation?

The Magic Blueprint (The Algorithm)

The authors discovered a clever way to solve this using a mathematical tool called Linear Programming. Imagine you have a giant blueprint for the party, but instead of drawing solid lines, you draw "fuzzy" lines that show how likely it is that two people should be separated. This blueprint is a bit like a recipe that tells you the probability of cutting a hand-hold.

The trick they used is called "flattening." Instead of trying to build the whole tree at once (which is like trying to bake a whole cake in one second), they broke the problem down into layers. They looked at the blueprint level by level. At each level, they asked: "Who needs to be in a 'good shape' group right now?" and "Who needs to be separated to keep the groups small?"

They found that for two specific types of shapes, they could build a very good approximation of the perfect tree:

Trees (T): Groups that look like a branching tree structure.
Bounded Diameter (Dd): Groups where everyone is close to everyone else (like a small, tight circle).

For the Tree groups, they created an algorithm that gets within a factor of O(log n · log log n) of the perfect score.
For the Bounded Diameter groups, they got within a factor of O(log n).

In plain English, this means their method isn't perfect, but it's very good, and it runs fast enough to be useful. They proved this works by showing that if you have a good way to solve a simpler problem (like cutting a graph to remove cycles or separate specific pairs), you can use that to build the whole hierarchy.

The Hard Truth (Why We Can't Do Better)

However, the paper also delivers a bit of bad news. The authors showed that if you want a perfect solution, or even a solution that is just "pretty close" (within a constant factor), you are out of luck.

They proved that under a famous computer science assumption called the Small Set Expansion Hypothesis, it is impossible to create an algorithm that guarantees a perfect or near-perfect score for these problems. In other words, the "best" way to sort these groups is likely too hard for any computer to figure out quickly. The gap between "good enough" (which they found) and "perfect" (which they proved is impossible) is a fundamental wall in computer science.

Why This Matters

Why should a curious teenager care? Because this isn't just about math; it's about how we organize the world.

File Systems: Imagine your computer's folders. Usually, they go all the way down to individual files. But sometimes, a whole folder of "Summer Vacation Photos" is a perfect final group. This research helps computers decide when to stop digging.
Online Shopping: Think of an online store. You might want to group products into "Electronics," then "Laptops," but maybe the final group "Gaming Laptops" is a big, diverse bunch that doesn't need to be split into single items. This method helps build those categories automatically.
Dynamic Updates: The authors suggest a cool idea: you could build a static "skeleton" tree where the leaves are these nice, tidy groups. If a group gets too messy or you need more detail later, you can just zoom in and refine that specific leaf. It saves space and time.

The Bottom Line

Szyfelbein and Dereniowski have handed us a new toolkit. They showed that while we can't magically find the absolute perfect way to stop our data-sorting party early, we can find a really, really good way to do it quickly. They built a general framework that works for trees and tight circles, and they proved that trying to do better than that is likely a fool's errand. It's a victory for "good enough" in a world where "perfect" might be impossible.

Technical Summary: Hierarchical F-Clustering: Approximation and Hardness

1. Problem Definition

The paper introduces Hierarchical F-Clustering (HC-F), a generalization of the classical Hierarchical Clustering problem. In standard hierarchical clustering, a dataset (represented as a weighted graph $G$ ) is recursively partitioned until every cluster is a singleton. The quality of a solution is measured by Dasgupta's objective, which penalizes cutting edges with high similarity early in the hierarchy (i.e., when the cluster size is large).

In the HC-F variation, the recursive process is allowed to terminate whenever a cluster belongs to a specific graph class $\mathcal{F}$ . The goal remains to minimize Dasgupta's objective, but the leaf nodes of the resulting clustering tree must be graphs belonging to $\mathcal{F}$ rather than singletons. The authors focus on two natural choices for $\mathcal{F}$ :

Trees ( $\mathcal{T}$ ): Clusters that are acyclic.
Bounded Diameter Graphs ( $\mathcal{D}_d$ ): Clusters where the diameter (maximum distance between any two nodes) is at most $d$ .

The paper assumes $\mathcal{F}$ is a non-empty class closed under subgraphs and recognizable in polynomial time.

2. Methodology and Framework

The authors propose a general framework for approximating HC-F for graph classes they term $\alpha(n)$ -well-behaved. The core methodology relies on a "flattening" technique, decomposing the hierarchical problem into a sequence of "flat" partitioning problems, guided by Linear Programming (LP).

2.1 The $\alpha(n)$ -Well-Behaved Condition

A graph class $\mathcal{F}$ is $\alpha(n)$ -well-behaved if the associated $p\mathcal{F}$ -Partitioning ( $p\mathcal{F}$ -P) problem admits:

A natural Integer Linear Programming (ILP) formulation using edge-cut variables.
Constraints encoded as "cover-type" constraints (e.g., $\sum_{e \in R} y_e \geq 1$ ) that ensure a structural predicate $p_\mathcal{F}$ is satisfied for a set of terminals.
An LP relaxation solvable in polynomial time.
A rounding algorithm that, given an LP solution, produces a valid cut with cost at most $\alpha(n)$ times the LP cost.

Examples of $p\mathcal{F}$ -P include:

Feedback Edge Set (FES): Removing edges to break cycles through terminals (relevant for Trees).
Min-Multicut (MMC): Disconnecting specific pairs of terminals (relevant for Bounded Diameter).
$\rho$ -Separator: Partitioning the graph so components containing terminals have bounded weight.

2.2 The Algorithmic Framework

The algorithm proceeds in two main phases:

Phase 1: Preprocessing and LP Relaxation
The authors construct an ILP (ILP-HC-F) that encodes the hierarchical structure using level-based variables.

Variables $y^t_e$ indicate if edge $e$ is cut at level $t$ (where levels correspond to cluster weights).
Variables $x^t_v$ indicate if vertex $v$ satisfies the $\mathcal{F}$ -predicate at level $t$ .
The formulation includes spreading-metrics constraints (adapted from Charikar and Chatziafratis) to ensure clusters are sufficiently separated and refinement constraints to maintain the hierarchical structure.
The ILP is relaxed to an LP (LP-HC-F) and solved. A rounding procedure sets $x^t_v = 1$ if $x^t_v \geq 1/2$ and scales edge variables $y^t_e$ by 2, yielding a partially integral solution.

Phase 2: Recursive Construction
The algorithm builds the clustering tree top-down:

For a current cluster $H$ , it identifies vertices that satisfy the $\mathcal{F}$ -predicate ( $X_1$ ) and those that do not ( $X_0$ ) at a specific level $t = w(H)/2$ .
Cut 1 ( $E_F$ ): It uses the LP solution restricted to $X_1$ as a guide for the $p\mathcal{F}$ -P problem. An $\alpha(n)$ -approximation algorithm for $p\mathcal{F}$ -P is run to cut edges, ensuring vertices in $X_1$ satisfy the predicate.
Cut 2 ( $E_\rho$ ): It uses the LP solution restricted to $X_0$ as a guide for the $\rho$ -Separator problem (with $\rho=1/2$ ). A bicriteria approximation algorithm (with ratio $\beta(n) = O(\log n)$ ) cuts edges to ensure remaining components are small enough (weight $\leq 2/3$ of the parent).
The union of cuts partitions $H$ into smaller components, which are processed recursively.

3. Key Results

3.1 Approximation Algorithms

The main theorem states that if $\mathcal{F}$ is $\alpha(n)$ -well-behaved, there exists an $O(\alpha(n) + \beta(n))$ -approximation algorithm for HC-F, where $\beta(n) = O(\log n)$ is the approximation ratio for the $\rho$ -Separator problem.

Applying this to the specific classes:

Hierarchical Tree Clustering (HC- $\mathcal{T}$ ): Since the Feedback Edge Set problem admits an $O(\log n \cdot \log \log n)$ -approximation via LP rounding, the authors achieve an $O(\log n \cdot \log \log n)$ -approximation for HC- $\mathcal{T}$ .
Hierarchical Bounded Diameter Clustering (HC- $\mathcal{D}_d$ ): Since the Min-Multicut problem admits an $O(\log n)$ -approximation, the authors achieve an $O(\log n)$ -approximation for HC- $\mathcal{D}_d$ .

These are presented as the first polynomial-time approximation algorithms for these specific HC-F variants.

3.2 Hardness of Approximation

The paper establishes strong inapproximability results under the Small Set Expansion Hypothesis (SSEH):

Both HC- $\mathcal{T}$ and HC- $\mathcal{D}_d$ cannot be approximated within any constant factor.
The proof involves a black-box reduction from the inapproximability of classical Hierarchical Clustering.
- For HC- $\mathcal{D}_d$ , the reduction attaches gadgets of diameter $d$ to every vertex, forcing the algorithm to treat the gadget as a representative of the original vertex.
- For HC- $\mathcal{T}$ , the reduction attaches triangles to vertices. The authors leverage the property that the cost of the optimal Hierarchical Clustering is lower-bounded by the Minimum Linear Arrangement (MLA) cost, showing this lower bound holds for the constructed instances as well.

4. Significance and Claims

The paper claims to provide the first algorithmic results for the Hierarchical F-Clustering problem. Its primary contribution is a general framework that unifies the approximation of hierarchical clustering into various structural classes, provided those classes satisfy the $\alpha(n)$ -well-behaved condition.

The authors emphasize that their approach is not limited to trees or bounded diameter graphs but applies to any class where the corresponding flat partitioning problem (like Multiway Cut) admits a natural ILP formulation with provable rounding guarantees. They note that improving these approximation ratios beyond the $O(\log n)$ factor would likely require breakthroughs in the approximation of fundamental cut and separator problems (like Sparsest Cut or Multicut), which are currently believed to be hard to improve.

The work also highlights practical motivations, such as the need for clustering structures that stop at "simple" components (like directories in file systems or product categories in e-commerce) rather than forcing all clusters to singletons, thereby encoding meaningful granularity levels.