**Background and notation:**

Whenever I speak of a *hypergraph* $G$, I mean a pair of finite sets $V_G,E_G$ and a function $g\colon E_G\to\mathbb{P}(V_G)\;$ assigning each edge a subset of vertices.

If $v\in V_G$ is a vertex, let $E_v=\{e\in E_G\mid v\in g(e)\}\;$ be the set of edges containing $v$; the cardinality $\#E_v$ is called the *degree of $v$*.

For $n\in\mathbb{N}$, let $E^n_G=\{e\in E_G\mid\#g(e)=n\}\;$ denote the set of $n$-ary edges. Suppose $v\in V_G$ is a vertex; we denote by $E^1_v=E_v\cap E^1_G$ the set of singleton edges at $v$.

**Clustering, its cost, and the goal:**

We define an operation on hypergraphs, called clustering: contracting a set of vertices and removing the resultant singleton edges. This operation can be repeated until the hypergraph is a single vertex with no edges, which we call the *point*. The process of clustering until we reach the point will be called a *complete reduction of $G$*. Each time we cluster, there is an associated cost, which we explain at the bottom of this section. The cost of a complete reduction is the maximum cost incurred in the process. The goal is to find a strategy that minimizes the cost of completely reducing $G$.

Given a vertex $v$, the *singleton edge removal at $v$* is the hypergraph $G'=G-E^1_v$ with the same vertices but the singleton edges at $v$ removed $E_{G'}=E_G-E^1_v$. The cost for removing singleton edges at $v$ is its degree $\#E_v$.

Given a subset $C\subseteq V_G$, the *contraction of $G$ by $C$*, denoted $G/C$ is the result of identifying those vertices in $C$ to become a single vertex $v_C$. There is a natural bijection between the edges before and after a contraction, $E_G\cong E_{G/C}$. However, note that there are may be new 1-ary edges created by contraction.

By *clustering* a subset of vertices $C\subseteq V_G$, we mean contracting it to a single vertex $v_C$ and then removing singleton edges at $v_C$.

The cost for clustering is just the cost of the singleton-edge-removal step.

**Examples:**

- We can always cluster the entire hypergraph $G$ at once. The contraction $G/V_G$ will have as many edges as $G$ but they all become 1-ary. Removing them, and thus completely reducing $G$, has a cost of $\#E_G$. This is generally the worst strategy.
- Suppose that $G$ is the chain $*-*-*-*-*$. Contracting the first two vertices, we obtain $-*-*-*$; removing the singleton costs 2 and the result is $*-*-*$. We can repeat twice more, moving left to right, and the maximum cost incurred is 2. This is a cost-minimizing strategy, though note that there are several cost-minimizing strategies in this case.
- For any hypergraph $G$, one can define a
*greedy algorithm*that looks for pairs of vertices for which the cost of clustering is minimized. This strategy does not always win.

**Questions:**

- Does this clustering question have a name?
- Does it relate to known questions that have been studied?
- Any ideas for an efficient algorithm?