Keywords: Graph partitioning with demands, Generalized conductance, Sparsest cut, Generalized multicut, Hierarchical clustering, Approximation algorithms.



1 Introduction↩︎

Sparsest Cut is a central problem among various graph partitioning tasks. Given a graph \(G=(V,E, c)\), where \(c\colon E \to \mathbb{N}\) is a capacity function, the goal is to find a subset of vertices \(S\subseteq V\) that minimizes

\[\phi\mathopen{}\left( S \right) = \frac{c\mathopen{}\left( S, \bar{S} \right)}{\mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right|}.\] where \(\bar{S}=V\setminus S\) and \(c\mathopen{}\left( S,\bar{S} \right)=\sum_{u\in S}\sum_{v \in \bar{S}}c\mathopen{}\left( u, v \right)\).

This problem has been extensively studied in the literature [1] resulting in remarkable connections to topics including metric spaces [2]–[5] and spectral graph theory [6]–[8] with the state-of-the-art approximation algorithm due to Arora, Rao, and Vazirani [9], achieving ratio of \(\mathcal{O}\mathopen{}\left( \sqrt{\log n} \right)\), where \(n=\mathopen{}\left| V \right|\). Moreover, it also has a number of applications as an essential primitive in other graph algorithms, where it serves as a building block for various divide-and-conquer strategies. This includes Graph Partitioning where the goal is to find a subset of edges of minimum capacity such that all of the connected components resulting from deleting these edges are of small size [1]. Another example is the problem of Hierarchical Clustering with similarity measures, where the goal is to hierarchically cluster data points, so that to minimize the Dasgupta’s clustering objective [10]–[12]. Intuitively, this objective promotes clusters with both children of balanced size as well as a low capacity of edges cut between them. In particular, given an \(\alpha\)-approximation algorithm for the Sparsest Cut, one can obtain an \(\mathcal{O}\mathopen{}\left( \alpha \right)\)-approximation algorithm for both of the aforementioned problems.

This usefulness of Sparsest Cut can be attributed to the following observation, implicitly exploited by many algorithms [1], [3], [10]–[13]. The quantity \(\mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right|\) can be interpreted in two separate ways. First, imagine each pair of vertices to be associated with a unit demand. Then, \(\mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right|\) can be seen as the total demand crossing the cut. This interpretation is useful for the sake of developing approximation algorithms for the Sparsest Cut itself, since a weak duality between Sparsest Cut and multicommodity flow type problems has been established [1], [3]. Secondly, \(\mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right|\) can be observed to be large when both partitions are of roughly equal size. This comes useful when developing divide-and-conquer algorithms for other graph problems [1], [9], [13], since the product in the denominator becomes a measure of the balance of a cut.

However, if one were to generalize Sparsest Cut to general demand setting, these two interpretations are no longer equivalent. Let \(w\colon V\times V\to \mathbb{N}\) be the demand function. The Generalized Sparsest Cut is to find a subset of vertices \(S\subseteq V\) that minimizes \[\phi_w\mathopen{}\left( S \right) = \frac{c\mathopen{}\left( S, \bar{S} \right)}{w\mathopen{}\left( S, \bar{S} \right)}.\] This problem is also well-understood, and the state-of-the-art approximation algorithm is due to Arora, Lee, and Naor [5], which achieves the ratio of \(\mathcal{O}\mathopen{}\left( \sqrt{\log n}\cdot \log \log n \right)\). However, as discussed above, in order to use some notion related to sparsity in a wider range of applications, it would be desirable to approximate some quantity measuring the balance of a cut. To the best of our knowledge, no such results have been obtained in the literature yet. Moreover, the above quantity may assign very large value to a cut \((S, \bar{S})\) even if the cut is very balanced. Consider for example the case when both partitions have internal demand \(w\mathopen{}\left( S \right)=w\mathopen{}\left( \bar{S} \right)=w\mathopen{}\left( V \right)/2\) but the demand between them is \(w\mathopen{}\left( S, \bar{S} \right) = 0\). Then, (by our convention) \(\phi_w\mathopen{}\left( S \right)=\infty\), even though the cut is perfectly balanced. This motivates us to focus on a different graph parameter. The graph conductance is a well-known measure of the balance of a cut, defined as \[\psi\mathopen{}\left( S \right) = \frac{c\mathopen{}\left( S, \bar{S} \right)}{\operatorname{vol}(S)\cdot \operatorname{vol}(\bar{S})}.\] where \(\operatorname{vol}(S)=\mathopen{}\left| \mathopen{}\left\{ e\in E\colon e\cap S\neq \emptyset \right\} \right|\)¹. In fact, for the case of unit demands, minimizing the conductance is equivalent to the Sparsest Cut, up to a constant factor. However, for the general demands this is not a case, and this will come useful in our applications. The generalized conductance of a cut \(\mathopen{}\left( S,\bar{S} \right)\) will be defined as \[\psi_w\mathopen{}\left( S \right) = \frac{c\mathopen{}\left( S, \bar{S} \right)}{w\mathopen{}\left( S, V \right)\cdot w\mathopen{}\left( \bar{S}, V \right)},\] where \(w\mathopen{}\left( X,V \right)=w\mathopen{}\left( X \right)+w\mathopen{}\left( X,V\setminus X \right)\). The problem of \(\psi_w\) minimization will be called the Generalized Conductance. We initiate the study of this problem by providing an \(\mathcal{O}\mathopen{}\left( \log n \right)\)-approximation algorithm for general graphs. Interestingly enough, in our algorithm we use a non-trivial reduction to the former Generalized Sparsest Cut. However, we additionally require in this reduction that the amount of demand cut is not too large. This is crucial for the analysis of the reduction, and it turns out that this additional constraint can be handled by a combination of known techniques. At the core of our method are algorithmic reductions to few cut-like problem, including the one just mentioned as an example, and the notion of cut-sparsifier tree decompositions by Räcke [14] which allow us to simplify the problem by reducing it to solving tree instances.

1.1 Our results and techniques↩︎

In this work, we show a series of algorithmic reductions between various graph partitioning tasks. The Generalized Conductance turns out to be the central one of them. Due to this we structure our work into two main parts, the first concerned with the latter problem and the second with its applications. Our main result is the following corollary:

To obtain the above result, we combine a variety of techniques in order to simplify the problem to some easy enough primitive task. Intuitively, our algorithm is sensitive to two types of instances which are tackled differently. Although they are never distinguished explicitly, by choosing the best among two obtained solutions we get a non-trivial approximation ratio of \(\mathcal{O}\mathopen{}\left( \log n \right)\). The two cases are dictated by the size of \(w\mathopen{}\left( S^*, \bar{S^*} \right)\) in an optimal solution. If this quantity is large, then the problem (up to a constant factor approximation loss) essentially becomes the well known \(k\)-Multicut problem, where the task is to find a minimum cost partition of the graph while ensuring that at least \(k\) units of demand are cut in total. This problem admits an \(\beta=\mathcal{O}\mathopen{}\left( \log n \right)\)-approximation algorithm by combining [15] with [14]. Such a solution is not fully suitable for our purposes, because the number of connected components obtained via \(k\)-Multicut might be arbitrarily large. To remedy this we employ a Max-Cut algorithm which ensures that a significant portion of the demand is still cut while partitioning the components into two groups as required.

If the aforementioned quantity is small, then we show that we can reduce the problem to the Generalized Sparsest Cut with additional constraint that the demand to be cut cannot be too large. This is done by constructing an auxiliary graph with new demand function such that cutting demand in this new instance roughly corresponds to minimizing the conductance in the original instance. This reduction preserves the approximation ratio, however its analysis is sensitive and crucially relies on the fact that \(w\mathopen{}\left( S^*, \bar{S}^* \right)\) is assumed to be of small value.

In order to tackle this constrained version of the Sparsest Cut we use a general technique of Räcke [14]. The idea is to embed a graph into a polynomial-sized convex combination of trees, which in expectance preserves the value of any cut up to \(\mathcal{O}\mathopen{}\left( \log n \right)\) distortion. This allows us to obtain the \(\mathcal{O}\mathopen{}\left( \log n \right)\)-approximation by solving the problem to optimality on all trees and outputting the best of the solutions. This indeed becomes an easy task, since the (unconstrained) Sparsest Cut can be found in a tree by only considering single-edge cuts. As it turns out, the same is true for the constrained version of the problem.

In the second part of the paper we move ourselves towards applications of the Generalized Conductance. We argue that, given constants \(0< \rho< \eta <1\) and a \(\gamma\)-approximation algorithm for the Generalized Conductance, its iterative application partitions the graph into components with demand at most \(\eta\cdot w\mathopen{}\left( V \right)\) while paying only² \(\mathcal{O}_{\rho, \eta}\mathopen{}\left( \gamma \right)\) times more than it is required to partition the graph into components with demand at most \(\rho\cdot w\mathopen{}\left( V \right)\). This gives the following corollary:

Then, we show that the above bicriteria approximation algorithm can be used to obtain an \(\mathcal{O}\mathopen{}\left( \log \gamma \right)\)-approximation for Hierarchical Clustering with Demands. This is done in a recursive top-down manner. A single call to the algorithm partitions the graph into components with ‘internal’ demand at most \(\frac{4}{5}\cdot w\mathopen{}\left( V \right)\). Then, the rest of hierarchy is built by applying the algorithm recursively in those of the resulting components that need to be further partitioned. Using a tight analysis generalizing the framework of [11] we show that the approximation ratio is indeed preserved.

Figure 1 outlines the algorithmic reductions that appear in this work.

1.2 Related work↩︎

The modern approximation theory of Sparsest Cut starts from approximate max-multicommodity flow/min-sparsest cut duality. By exploiting this duality, Leighton and Rao provide an \(\mathcal{O}\mathopen{}\left( \log n \right)\)-approximation [1] for the Sparsest Cut. Aumann and Rabani refine this to \(\mathcal{O}\mathopen{}\left( \log k \right)\) when only \(k\) demand pairs are relevant [3]. Those results were then improved by Arora-Rao-Vazirani by exhibiting an \(\mathcal{O}\mathopen{}\left( \sqrt{\log n} \right)\) approximation for Uniform Sparsest Cut [9]. Obtaining these results required a new approach based on semidefinite programming and high-dimension geometry, which was then further refined by Arora, Lee, and Naor to obtain an \(\mathcal{O}\mathopen{}\left( \sqrt{\log n}\cdot \log\log n \right)\)-approximation for general demands [5]. On hardness, Chawla, Krauthgamer, Kumar, Rabani, and Sivakumar show (under UGC) that Multicut and Sparsest Cut are hard to approximate within any constant factor; moreover, a quantitatively stronger UGC implies an inapproximability factor of \(\Omega\mathopen{}\left( \sqrt{\log\log n} \right)\) [16]. Khot-Vishnoi further show UGC-based super-constant hardness for Non-Uniform Sparsest Cut and prove a \(\mathopen{}\left( \log\log n \right)^{1/6-\delta}\) lower bound/integrality gap for the associated SDP/embedding relaxation, for every fixed \(\delta>0\) [17]. Raghavendra-Steurer connect this picture to Small-Set Expansion by relating expansion hardness and UGC [18].

1.2.0.1 Graph partitioning, Separators and Hierarchical clustering.

Balanced Graph Partitioning is a problem of partitioning a graph into \(k\) clusters, each of size roughly \(n/k\) as to minimize the cost of the cut edges. Krauthgamer, Naor, and Schwartz study \(k\)-Balanced Partitioning and give a bi-criteria approximation ratio of \(\mathcal{O}\mathopen{}\left( \sqrt{\log n\cdot \log k} \right)\); they also show an \(\Omega\mathopen{}\left( \log k \right)\) integrality gap for their SDP relaxation [19]. A related separator ‘machinery’ is developed by Feige, Hajiaghayi, and Lee, who obtain an \(\mathcal{O}\mathopen{}\left( \sqrt{\log n} \right)\) approximation for Min-Ratio Vertex Cut, a vertex analogue of the Sparsest Cut which gives an \(\mathcal{O}\mathopen{}\left( \sqrt{\log n} \right)\) pseudo-approximation for Vertex Separators in general graphs [13]. The latter problem is to remove a ‘cheap’ subset of vertices so that the remaining graph consists of two pieces of small size. A hierarchical analogue of Graph Partitioning is the problem of Hierarchical Clustering, where the goal is to recursively partition the graph into more refined clusters until all of them become singletons. Dasgupta introduced the now-standard similarity-based objective and analyzed a top-down algorithm based on repeated Sparsest Cuts, obtaining an \(\mathcal{O}\mathopen{}\left( \alpha\cdot\log n \right)\) guarantee when Uniform Sparsest Cut admits an \(\alpha\)-approximation [10]. Charikar and Chatziafratis tightened this analysis to \(\mathcal{O}\mathopen{}\left( \alpha \right)\) (thus \(\mathcal{O}\mathopen{}\left( \sqrt{\log n} \right)\) using ARV), and additionally gave an SDP relaxation with integrality gap at most \(\mathcal{O}\mathopen{}\left( \sqrt{\log n} \right)\) [11]. Authors in [12] obtain similar results but using a different argument. Recently, an \(\mathcal{O}\mathopen{}\left( \sqrt{\log n} \right)\)-approximation was also obtained for the vertex variant of this problem where at each level of the hierarchy a subset of nodes is removed from the graph [20].

1.2.0.2 Metric spaces and embeddings.

Metric embeddings are a crucial concept required for approximating graph partitioning tasks. The Bourgain theorem implies that every finite metric embeds into Hilbert space with logarithmic distortion; this has direct algorithmic consequences for cut and partition objectives through embedding-based relaxations and rounding [4]. Embedding such metrics and subsequent refinements for negative-type metrics are key ingredients in the progression from \(\mathcal{O}\mathopen{}\left( \log n \right)\)-type to sub logarithmic approximations for the Sparsest cut [2], [5]. In parallel, tree-metric reductions and cut-preserving decompositions (in particular Räcke’s hierarchical decompositions) provide an alternative way of obtaining provable guarantees: one transfers the task of partitioning a general graph into partitioning trees, which usually can be done in exactly or with a constant-factor approximation ratio. Such a transformation incurs only logarithmic distortion in expectation [14].

1.2.0.3 Spectral graph theory and sparsest cut.

The spectral graph theory relates the sparsity of the best cut to the eigenvalues of the graph Laplacian through Cheeger-type inequalities. In its original, geometric form, Cheeger’s inequality concerns a compact Riemannian manifold \(M\) and lower bounds the smallest positive eigenvalue \(\lambda_1\) of the Laplace-Beltrami operator by the square of the isoperimetric (Cheeger) constant \(h(M)=\inf_{S}\frac{\operatorname{area}(S)}{\min\mathopen{}\left( \operatorname{vol}(A),\operatorname{vol}(B) \right)}\), where the hypersurface \(S\) ranges over separators splitting \(M\) into two parts \(A,B\); concretely, \(\lambda_1\geq h(M)^2/4\) [6]. Alon and Milman transported this phenomenon to graphs, proving a two-sided discrete analogue that ties the second-smallest eigenvalue \(\lambda_2\) of the (normalized) Laplacian to the graph conductance \(\phi(G)\), namely \(\tfrac{1}{2}\lambda_2\leq \phi(G)\leq \sqrt{2\lambda_2}\) [7].³ Thus a graph has no sparse (low-conductance) cut exactly when its spectral gap is large. Moreover, the inequality is algorithmic, since sweeping over the coordinates of the eigenvector of \(\lambda_2\) (the Fiedler vector) extracts a cut of conductance \(\mathcal{O}\mathopen{}\left( \sqrt{\phi(G)} \right)\), a quadratic approximation of the optimum. Building on this connection, Spielman and Teng [8] showed that spectral partitioning is provably good: they establish \(\lambda_2=\mathcal{O}\mathopen{}\left( 1/n \right)\) for bounded-degree planar graphs and \(\lambda_2=\mathcal{O}\mathopen{}\left( 1/n^{2/d} \right)\) for well-shaped \(d\)-dimensional finite-element meshes, and turn these eigenvalue bounds into separators of size \(\mathcal{O}\mathopen{}\left( \sqrt{n} \right)\) (respectively \(\mathcal{O}\mathopen{}\left( n^{1-1/d} \right)\)) obtained from the Fiedler vector.

1.2.0.4 Sparsity, expanders, and complexity applications.

Sparsest Cut is the algorithmic counterpart of edge expansion: a graph is an expander precisely when it has no sparse cut, i.e. every set \(S\) with \(\mathopen{}\left| S \right|\leq \mathopen{}\left| V \right|/2\) satisfies \(c\mathopen{}\left( S,\bar{S} \right)\geq \Omega\mathopen{}\left( \mathopen{}\left| S \right| \right)\). This duality is exactly what expander-flow techniques exploit: Arora, Rao, and Vazirani certify expansion by routing an “expander flow” inside the graph, which underlies their \(\mathcal{O}\mathopen{}\left( \sqrt{\log n} \right)\) approximation [9]. Beyond partitioning, expansion is a resource in its own right. Sipser and Spielman use constant-degree expanders to construct expander codes: asymptotically good linear codes, of constant rate and constant relative distance, for which a simple bit-flipping decoder corrects a constant fraction of errors in linear time, with the correctable fraction controlled directly by the expansion of the underlying graph [21]. Expansion is likewise central to the PCP theorem, which asserts that every NP statement admits a proof verifiable by reading only \(\mathcal{O}\mathopen{}\left( 1 \right)\) bits of the proof and using only \(O\mathopen{}\left( \log n \right)\) random bits [22]. A surprising proof of PCP by Dinur’s reaches it through repeated gap amplification, where each round first turns the constraint graph into an expander and then boosts the unsatisfiability gap by a constant factor via graph powering, the analysis of which rests on the spectral gap of that expander [23].

2 Preliminaries↩︎

Most instances of the problems considered in this work consist of a graph \(G=\mathopen{}\left( V,E,c,w \right)\), where \(V\) is the vertex set, \(E\) is the edge set, \(c\colon E \to \mathbb{N}\) is the capacity function which encodes the cost of cutting an edge, and \(w\colon V\times V\to \mathbb{N}\) is the demand function which, informally speaking, tells how important separating a given vertex pair is. For adjacent vertices \(u,v\in V\), we denote by \(uv\) the edge between \(u\) and \(v\). For any \(C\subseteq E\), \(G\setminus C\) is the graph obtained by removing the edges in \(C\) from \(G\). We write \(\mathopen{}\left( V_H,E_H,c_H,w_H \right)\) to point out that given parameters represent a particular graph or subgraph \(H\), different than \(G\).

For any function \(f\colon V\times V\to \mathbb{N}\) and disjoint subsets \(A, B\subseteq V\), we define: \[f\mathopen{}\left( A \right)=\sum_{u,v\in A}f\mathopen{}\left( u, v \right), \quad f\mathopen{}\left( A, B \right)=\sum_{u\in A}\sum_{v\in B}f\mathopen{}\left( u, v \right)\] with a convention that if the domain of \(f\) is the edge set and \(uv\notin E\), then \(f\mathopen{}\left( u,v \right)=0\). Whenever \(A, B\subseteq V\) are not disjoint, we define \(f\mathopen{}\left( A, B \right)=f\mathopen{}\left( A \right)+f\mathopen{}\left( A, B\setminus A \right)\) (see Figure 2 for an illustration). For a subset \(C\subseteq E\) and a function \(f\) on the edge set, \(f\mathopen{}\left( C \right)=\sum_{e\in C}f\mathopen{}\left( e \right)\). For a subset \(S\subseteq V\), we denote by \(\bar{S}\) the complement of \(S\) in \(V\), i. e. \(\bar{S}=V\setminus S\). A cut is any subset \(S\subseteq V\), such that \(S\neq \emptyset\), \(S\neq V\) and we denote it either by just \(S\) or we write \(\mathopen{}\left( S, \bar{S} \right)\) to explicitly indicate the two sides of the cut. It will be sometimes more convenient to call a cut the set of edges having one endpoint in \(S\) and the other in \(\bar{S}\). Which definition is used will be clear from the context. For any cut-based objective function \(F\) used in this paper, \(F\mathopen{}\left( S \right)\) or \(F\mathopen{}\left( S, \bar{S} \right)\) denote the value of \(F\) on a specific cut \(S\), whereas \(F\mathopen{}\left( G \right)\) denotes the optimum value of \(F\) over all cuts of the graph \(G\). Moreover, whenever an objective function is given as a ratio and its denominator equals \(0\), we set the value of this objective to \(\infty\).



3 The main algorithm↩︎

In order to tackle the Generalized Conductance, we simplify the optimization criterion by considering the following problem: for a given input graph \(G=(V,E,c,w)\), find a cut \(S\) that minimizes the following: \[\label{eq:h} h_w^{\delta}\mathopen{}\left( S \right)=\frac{c\mathopen{}\left( S, \bar{S} \right)}{w\mathopen{}\left( S, V \right)}, \quad \text{subject to} \quad w\mathopen{}\left( \bar{S}, V \right)\geq \delta\cdot w\mathopen{}\left( V \right)\tag{1}\] for some constant \(0<\delta\leq 1\) to be determined later. We refer to the above as the Simplified Conductance problem. We have the following observation.

We now list three problems that will be used as black-box subroutines in our main algorithm below. First, we will use the Generalized Sparsest \(K\)-Bounded Cut that adds a demand restriction to the classic Generalized Sparsest Cut (cf. step [it:S1:alpha] of the algorithm below). Formally, given a graph \(G=(V,E,c,w)\), we consider the problem of finding \(S\) that minimizes: \[\label{eq:K} \phi_w^{K}\mathopen{}\left( S \right) = \frac{c\mathopen{}\left( S,\bar S \right)}{w\mathopen{}\left( S,\bar S \right)} \quad\text{subject to}\quad 0<w\mathopen{}\left( S,\bar S \right)\le K.\tag{2}\]

We will also utilize (cf. step [it:S2:beta]) the Generalized \(k\)-Multicut: given a graph \(G=(V,E,c,w)\) with capacities and demands, find a minimum-cost set of edges \(C\subseteq E\), such that the demand cut by \(C\) is at least \(k\).

Finally, we recall the classical Max-Cut problem, where for a given graph \(G\), as finding a cut \(\mathopen{}\left( C_G, \bar{C}_G \right)\) that maximizes \(w\mathopen{}\left( C_G, \bar{C}_G \right)\). To solve the latter (approximately due to its NP-hardness), we utilize a folklore greedy procedure (in step [it:S2:R-cut] below) that we recall in the following form.

We now introduce a reduction⁴ scheme (an algorithm) used in this section. The scheme is applied to an input graph \(G=(V,E,c,w)\) and it computes independently two candidate cuts \(S_1\) and \(S_2\) via two different methods. The returned solution is \(S_i\) that minimizes the generalized conductance. Formally, the scheme is the following:

1. Compute a candidate set \(S_1\) (see Figure 3):

   1. Build an auxiliary graph \(G'=(V',E',c_{G'},w_{G'})\) by adding to \(G\) a universal vertex \(r\), i.e. \(V'=V\cup\mathopen{}\left\{ r \right\}\) and \(E'=E\cup\mathopen{}\left\{ ru\colon u\in V \right\}\), setting the capacities to \(c_{G'}\mathopen{}\left( r,u \right)=0\) for each \(u\in V\) and \(c_{G'}\mathopen{}\left\{ u,v \right\}=c\mathopen{}\left\{ u,v \right\}\) for each \(u,v\in V\), and the demands to \(w_{G'}\mathopen{}\left( r,u \right)=\sum_{v\in V}w\mathopen{}\left( u,v \right)\) for each \(u\in V\) and \(w_{G'}\mathopen{}\left( u,v \right)=0\) for each pair \(u,v\in V\).

   2. Run an \(\alpha\)-approximation algorithm for the Sparsest \(K\)-Bounded Cut with \(K=\frac{4}{3}\cdot w\mathopen{}\left( V \right)\). Denote the returned cut by \(S_1\).

2. Compute a candidate set \(S_2\) (see Figure 4):

   1. Run a \(\beta\)-approximation algorithm for the Generalized \(k\)-Multicut with \(k=w\mathopen{}\left( V \right)/3\) to obtain a multicut \(C\).

   2. Build a complete graph \(R\) whose vertices are the components of \(G\setminus C\), with edge weights \(w_R\mathopen{}\left( H_1,H_2 \right)=w\mathopen{}\left( V_{H_1},V_{H_2} \right)\) for any pair of components \(H_1\) and \(H_2\).

   3. Compute a cut \((C_R,\bar{C}_R)\) by solving Max-Cut on \(R\) by using Proposition 2.

   4. Map \((C_R,\bar{C}_R)\) back to a cut \(S_2\) in \(G\): \(S_2=\bigcup_{H\in C_R}V_H\).

3. Return the better of \(S_1,S_2\), i.e., \(\mathop{\mathrm{arg\,min}}_{X\in\mathopen{}\left\{ S_1,S_2 \right\}}\psi_w\mathopen{}\left( X \right)\).

Let for the rest of this section \(S_h^{*}\) be an optimal cut for the Simplified Conductance, where we without loss of generality assume \(w\mathopen{}\left( S_h^{*}, V \right)\le w\mathopen{}\left( \bar{S}_h^{*}, V \right)\). Our analysis consists of two separate cases depending on the size of \(w\mathopen{}\left( S_h^{*}, \bar{S}_h^{*} \right)\). First we prove (cf. Lemma 3) that if \(w\mathopen{}\left( S_h^{*}, \bar{S}_h^{*} \right)\) is sufficiently small, then the candidate solution \(S_1\) is the one that guarantees the required approximation ratio (determined in Section 4). The complementary case is handled by Lemma 4 (where the appropriate approximation ratio of \(\beta=\mathcal{O}\mathopen{}\left( \log n \right)\) will come from [14], [15]). (We remark that the exact choice of constants in our construction, like the one in Lemma 3, is somewhat arbitrary and we do not attempt to optimize them).

Now we analyze, the second case regarding the size of \(w\mathopen{}\left( S_h^{*}, \bar{S}_h^{*} \right)\), which is handled by the solution \(S_2\) found by the algorithm.

Lemmas 1, 3 and 4 give together the following result.

In the next section we develop an algorithm that determines the ratios of \(\alpha\). We finish this section with a remark that our method can be improved for a natural class of multiplicative demand functions. Formally, \(w\) is multiplicative if there exists a potential function \(\pi\colon V\to \mathbb{N}\) such that for every \(u,v\in V\), \(w\mathopen{}\left( u,v \right)=\pi\mathopen{}\left( u \right)\cdot \pi\mathopen{}\left( v \right)\). Notably, unit demand is multiplicative with \(\pi\mathopen{}\left( u \right)=1\) for every \(u\in V\). For such demand functions, we have the following strengthening of the approximation guarantee:



4 Algorithm for the sparsest \(K\)-bounded cut↩︎

Since solving tasks related to sparsest cut is easier on trees, an efficient approach to solving such problems is to first embed the graph into a tree while partially preserving the value of all cuts. To do so, one can use the cut-sparsifier tree decomposition of Räcke [14]. This decomposition allows for an embedding of any graph into a probability distribution over a polynomial number of trees such that for every cut, the expected value of the cut in the tree is at most \(\mathcal{O}\mathopen{}\left( \log n \right)\) times the value of the cut in the original graph, and for every cut, its value in the original graph is at most its value in every tree in the support of the distribution. Therefore, if we can solve our problem on trees, then we can solve it on general graphs with an \(\mathcal{O}\mathopen{}\left( \log n \right)\)-approximation ratio by first embedding it into a distribution over trees and then solving it on each tree in the support of the distribution. Then, the approximation ratio is achieved by choosing the best cut among all cuts produced for these trees. In what follows we formalize these ideas.

4.1 Decomposition trees and multicommodity flows↩︎

Given a graph \(G=(V,E,c)\), denote by \(P^*\) the set of all paths in \(G\). A decomposition tree for \(G\) is a rooted tree \(T=(V_T,E_T, c_T)\) together with:

1. a node map \(m_V:V_T\to V\) that is bijective on leaves of \(T\) and \(V\),

2. an edge map \(m_E:E_T\to P^*\) sending each tree edge \(uv\) to a path in \(G\) between the mapped endpoints \(m_V(u)\) and \(m_V(v)\),

3. induced maps \(m'_V:V\to V_T\) which maps each vertex of \(V\) to the corresponding leaf of \(T\) and \(m'_E:E\to P^*_T\) which maps an edge \(uv\in E\) to the unique (shortest) path between \(m'_V(u)\) and \(m'_V(v)\) in \(T\),

4. For a tree edge \(e=(u,v)\) of \(T\), let \(V_{u},V_{v}\) be the leaf partition induced by deleting \(e\). Its capacity is then defined as \[c_T(e)=\sum_{x\in V_{u}, y\in V_{v}} c(x,y).\]

A multicommodity flow in a graph \(G\) is a collection of flows \(f^{(i)}:E\to\mathbb{R}_{\ge 0}\) for \(i\in\mathopen{}\left\{ 1,\ldots,k \right\}\), where each flow \(f^{(i)}\) routes \(d_i\) units between a source-sink pair \((s_i,t_i)\). The flows needs to satisfy the demand constraints and should respect edge capacities.

The congestion of a multicommodity flow is a way to measure how much these capacities are violated. Formally, we define it as the maximum ratio of total flow to capacity over all edges: \[\xi_G = \max_{e\in E} \frac{\sum_{i=1}^{k} f^{(i)}(e)}{c(e)}.\] A multicommodity flow is feasible if its congestion is at most \(1\). Given a flow \(f\) in \(G\), we can map it to a flow in a decomposition tree \(T\) using the edge map \(m_E\). The mapped flow \(m'(f)\) is defined as follows: for each tree edge \(e_t\in E_T\), we sum the flow of all edges in \(G\) that are mapped to paths in \(T\) that include \(e_t\). Formally: \[m'(f)(e_t) = \sum_{e\in E: e_t\in m'_E(e)} f(e).\]

Räcke’s theorems relate the congestion of flows in a graph to the congestion in decomposition trees:

4.2 Cut value preservation bounds↩︎

For disjoint sets \(A,B\subseteq V\) and any graph \(G\), define \(\mathrm{min-cut}_{G}\mathopen{}\left( A,B \right)\) to be a cut \(C\) in \(G\) of minimum cost \(c_G\mathopen{}\left( C \right)\) that separates \(A\) from \(B\).

To bound how well cuts are preserved by Räcke’s decomposition, we use an argument analogous to max-flow/min-cut duality: capacities in each tree dominate the original cut capacities pointwise, and by combining tree flows through the convex decomposition we obtain a matching upper bound in expectation. This gives the following cut-value preservation statement.

4.3 Algorithm for the Generalized Sparsest \(K\)-Bounded Cut↩︎

Armed with Theorem 5, we can now show the main result of this section:



5 Applications↩︎

Below we show few applications of the Generalized Conductance. We show how to use the approximation algorithm for the Generalized Conductance to obtain approximation algorithms for the Quadratic Sparsest Cut, Graph Partitioning with Demands and Hierarchical Clustering with Demands problems.

5.1 A warm up: Quadratic Sparsest Cut↩︎

In the problem we call the Quadratic Sparsest Cut, one is required to find a subset of vertices \(S\) that minimizes \[\frac{c\mathopen{}\left( S, \bar{S} \right)}{\mathopen{}\left( \mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right| \right)^2}.\]

Observe, that if one assigns each pair of vertices \(u,v\) a demand of \(w\mathopen{}\left( u,v \right)=1\), then \[w\mathopen{}\left( S, V \right)\cdot w\mathopen{}\left( \bar{S}, V \right)=\mathopen{}\left( \mathopen{}\left| S \right|+\mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right| \right)\cdot \mathopen{}\left( \mathopen{}\left| \bar{S} \right|+\mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right| \right)=\mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right|+\mathopen{}\left| S \right|^2\cdot \mathopen{}\left| \bar{S} \right|+\mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right|^2+\mathopen{}\left( \mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right| \right)^2.\] Since \(\mathopen{}\left| S \right|,\mathopen{}\left| \bar{S} \right|\geq 1\), we get that \[\mathopen{}\left( \mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right| \right)^2\leq w\mathopen{}\left( S, V \right)\cdot w\mathopen{}\left( \bar{S}, V \right)\leq 4\cdot\mathopen{}\left( \mathopen{}\left| S \right|\cdot \mathopen{}\left| \bar{S} \right| \right)^2\] and the two objectives are equivalent up to a factor of \(4\). Since \(w\) is multiplicative, we obtain the following corollary:

5.2 Graph Partitioning with Demands↩︎

Below, we show how to use the approximation algorithm for the Generalized Conductance to obtain an approximation algorithm for Graph Partitioning with Demands. In the latter problem, we are given a graph \(G=(V,E,c,w)\) and a fixed constant \(\rho\in(0,1)\), and the goal is to find a subset of edges \(C\subseteq E\) that minimizes \(c\mathopen{}\left( C \right)\) such that for every \(H\in G\setminus C\), we have \(w\mathopen{}\left( V_H \right)\leq \rho\cdot w\mathopen{}\left( V \right)\). Let \(\text{OPT}_{\rho}\mathopen{}\left( G \right)=c\mathopen{}\left( C^* \right)\), where \(C^*\) is an optimal cut.

Let \(\rho<\eta<1\) be a constant. We will obtain a bi-criteria approximation algorithm for Graph Partitioning with Demands that returns a subset of edges \(C\) such that \(c\mathopen{}\left( C \right)=\mathcal{O}_{\rho, \eta}\mathopen{}\left( \gamma \right)\cdot \text{OPT}_{\rho}\mathopen{}\left( G \right)\) and for every \(H\in G\setminus C\), we have \(w\mathopen{}\left( V_H \right)\leq \eta \cdot w\mathopen{}\left( V \right)\), where \(\gamma\) is the approximation ratio for the Generalized Conductance. This is done in two parts. Firstly, we show an algorithm for a limited range of \(\eta\) and then extend it to the entirety of \(\eta\in(\rho,1)\).

Let \(\delta_{\rho}=\min\mathopen{}\left\{ 1/4,1-\rho \right\}\) and \(\eta\in\mathopen{}\left( \max\mathopen{}\left\{ 1/2,1-\delta_{\rho} \right\},1 \right)\). The analysis uses a generalization of the standard technique of dealing with Balanced Cut/Graph Partitioning problems using Sparsest Cut [1], [13]. However, due to the fact that we need to control both the demand in the components and the demand crossing the cut, a more careful consideration is required. The algorithm is simple:

1. \(C\gets\emptyset\)

2. \(G'\gets \mathopen{}\left( V, E,c,w \right)\)

3. While \(w_{G'}\mathopen{}\left( V_{G'} \right)> \eta \cdot w\mathopen{}\left( V \right)\) do

   • Use the \(\gamma\)-approximation algorithm for the Generalized Conductance to find a cut \((S,\bar{S})\) in \(G'\), where \(w_{G'}\mathopen{}\left( S \right)\leq w_{G'}\mathopen{}\left( \bar{S} \right)\).

   • \(C\gets C\cup E_{G'}\mathopen{}\left( S, \bar{S} \right)\)

   • Remove the vertices in \(S\) from \(G'\), i.e., \(G'\gets G'[V_{G'}\setminus S]\)

4. Return \(C\)

The above algorithm is characterized by the following claim.

As an immediate corollary we get:

Next, we show how to extend the above procedure into a recursive algorithm that works for any choice of \(0<\rho < \eta<1\). Since for \(\rho\geq 3/4\) the previous procedure works for any \(\eta\in(\rho,1)\), we focus on the case \(\rho<3/4\). In such case, observe that \(\delta_{\rho}=1/4\), and therefore we know, that the previous procedure works for any \(\eta\in(3/4,1)\).

Fix \(k'=\eta\cdot w\mathopen{}\left( V \right)\) and \(k=\rho\cdot w\mathopen{}\left( V \right)\) to be global parameters for the recursion, and note that \(k/k'=\rho/\eta\). Given a graph \(H\), the recursive algorithm proceeds as follows:

1. If \(w\mathopen{}\left( V_H \right)\leq k'\), return \(\emptyset\).

2. \(\eta_0\gets \max\mathopen{}\left\{ 4/5,\, k'/w\mathopen{}\left( V_H \right) \right\}\).

3. Run the algorithm of Theorem 7 on \(H\) with parameter \(\eta_0\) and let \(C\) be the returned subset of edges.

4. \(C_H\gets C\).

5. For every connected component \(H'\) of \(H\setminus C\), recursively partition \(H'\) and add the returned edges \(C_{H'}\) to \(C_H\).

6. Return \(C_H\).

As an immediate corollary we get:

5.3 Hierarchical clustering with demands↩︎

In this problem one is given a graph \(G=(V,E,c,w)\) with cost and demand functions \(c\colon E\to \mathbb{N}\) and \(w\colon V\to \mathbb{N}\), and the goal is to find a (hierarchical) clustering tree of \(G\). The clustering tree \(T=(V_T,E_T)\) of \(G\) is a binary tree where each node \(u\in V_T\) is associated with a subgraph \(H_u\) of \(G\), that we call a cluster, such that the subsets associated with children of \(u\) form a partition of \(H_u\). The root’s cluster is \(G\) and the leafs of \(T\) are associated with singletons. The Dasgupta’s clustering objective is to find a clustering tree \(T\) minimizing \[\label{eq:Dasgupta} \tilde{c}\mathopen{}\left( T \right) = \sum_{u\in V_T} w\mathopen{}\left( V_{H_u} \right)\cdot c\mathopen{}\left( V_{H_u}, V\setminus V_{H_u} \right).\tag{4}\] We refer to the above problem as Hierarchical Clustering with Demands. We show how to use the approximation algorithm for Graph Partitioning with Demands to obtain an approximation algorithm for the former task. We note that the assumption of \(T\) being binary can be relaxed since it is easy to see that any non-binary tree⁵ can be transformed into a binary one without increasing the cost [10].

The algorithm for Hierarchical Clustering with Demands is as follows:

1. Let initially \(T\) be a single (root) node associated with \(G\).

2. While \(T\) has a node \(u\) whose associated cluster is not a singleton, call a \(\gamma\)-approximation algorithm for Graph Partitioning with Demands on \(H_u\) with \(\rho=1/2\) and \(\eta=4/5\). Let \(C_u\) be the set of edges returned by the algorithm. For each connected component \(H\in H_u\setminus C_u\), add a child node \(v\) to \(u\) in \(T\) associated with the cluster \(H_v=H\).

In order to show that the above algorithm achieves an \(\mathcal{O}\mathopen{}\left( \gamma \right)\)-approximation ratio, where \(\gamma\) is the approximation ratio for the Graph Partitioning with Demands, we use a generalized decomposition technique into levels due to [11]. Denote by \(T^*\) a tree that minimizes the objective in 4 . Let \(\mathcal{H}_{t}\) be the set of all maximal clusters \(H\) in \(T^*\) such that \(w\mathopen{}\left( V_H \right)\leq t\). Observe that \(\mathcal{H}_t\) gives a partition of \(V\). Let \(E_t^*\) be the set of all edges between clusters in \(\mathcal{H}_t\). For convenience let \(E_0^*=E\). We call \(E_t^*\) the cut at level \(t\). We have the following lemma:

We also use the following upper bound on the \(\tilde{c}\mathopen{}\left( T^* \right)\) which is a direct consequence of the previous lemma:

Fix some non-leaf cluster \(H\) in the tree \(T\) computed by the algorithm and let \(C_H\) be the cut returned by the Graph Partitioning with Demands algorithm with input \(H\). Let \(r_H=w\mathopen{}\left( V_H \right)\) and \(s_H\) be the size of the largest child of \(H\) with respect to the total demand. With the above choice of \(\eta=4/5\), we have \(s_H\leq 4r_H/5\). The edges cut in \(H\) contribute \(r_H\cdot c\mathopen{}\left( C_H \right)\) to the objective function. We wish to charge this cost to the edges cut in \(E_{r_H/2}^*\), restricted to \(H\). We have the following bound: \[\begin{align} \mathopen{}\left( r_H-s_H \right)\cdot c\mathopen{}\left( E_{r_H/2}^*\cap E_H \right)\leq \sum_{t=s_H+1}^{r_H}c\mathopen{}\left( E_{\mathopen{}\left\lfloor t/2 \right\rfloor}^*\cap E_H \right) \end{align}\] since as the level \(t\) decreases, the more edges belong to \(E_t^*\).

The contribution of \(C_H\) to the objective \(\tilde{c}\mathopen{}\left( T \right)\) is: \[\begin{align} r_H\cdot c\mathopen{}\left( C_H \right) \leq 5\cdot\mathopen{}\left( r_H-s_H \right)\cdot c\mathopen{}\left( E_{r_H/2}^*\cap E_H \right)\leq 5\cdot \sum_{t=s_H+1}^{r_H}c\mathopen{}\left( E_{\mathopen{}\left\lfloor t/2 \right\rfloor}^*\cap E_H \right) \end{align}\] where the first inequality is due to the fact that \(r_H-s_H\geq r_H/5\).

Now, since all child clusters of \(H\) have size at most \(s_H\), they do not contribute to \(c\mathopen{}\left( E_{t}^* \right)\) for \(t > s_H\). Combining this observation with the fact that the clusters in \(T\) contributing to a given level \(t\) form a partition of \(V\), and thus are disjoint, we get that: \[\begin{align} \sum_{H} \sum_{t=s_H+1}^{r_H}c\mathopen{}\left( E_{t}^*\cap E_H \right) \leq \sum_{t=0}^{w\mathopen{}\left( V \right)} c\mathopen{}\left( E_{\mathopen{}\left\lfloor t/2 \right\rfloor}^* \right) \end{align}\]

Thus by summing up over the contribution of all cuts \(C_H\) we get that the cost of the tree returned by the algorithm is at most: \[\begin{align} \tilde{c}\mathopen{}\left( T \right)=\sum_{H} r_H\cdot c\mathopen{}\left( C_H \right) & \leq 5\cdot \sum_{H} \sum_{t=s_H+1}^{r_H}c\mathopen{}\left( E_{t}^*\cap E_H \right) \\ &\leq 5\cdot \sum_{t=0}^{w\mathopen{}\left( V \right)} c\mathopen{}\left( E_{\mathopen{}\left\lfloor t/2 \right\rfloor}^* \right)\leq 10\cdot \tilde{c}\mathopen{}\left( T^* \right) \end{align}\] where the last inequality is by the Corollary 7.

We get the following theorem:

And as an immediate corollary we get:

6 Conclusions↩︎

We introduced and studied the Generalized Conductance, a problem of interest on its own, and also important from the perspective of potential applications. Our main algorithm combines two complementary reductions which yield an \(\mathcal{O}\mathopen{}\left( \log n \right)\)-approximation on general graphs and an \(\mathcal{O}\mathopen{}\left( 1 \right)\)-approximation on trees. For multiplicative demand functions, we further improve the approximation guarantee to \(\mathcal{O}\mathopen{}\left( \sqrt{\log n} \right)\).

Beyond the core objective, we showed that these approximation ratios carry over to natural downstream tasks. In particular, we obtained an \(\mathcal{O}\mathopen{}\left( \log n \right)\) bicriteria approximation for Graph Partitioning with Demands and an \(\mathcal{O}\mathopen{}\left( \log n \right)\)-approximation for Hierarchical Clustering with Demands, with corresponding \(\mathcal{O}\mathopen{}\left( \sqrt{\log n} \right)\) guarantees in the multiplicative setting and \(\mathcal{O}\mathopen{}\left( 1 \right)\)-approximation for trees. These consequences indicate that generalized conductance can serve as a robust algorithmic primitive, similarly to how sparsest-cut-type objectives are used in classical divide-and-conquer methods. It is of interest whether our algorithm is applicable to different tasks in the presence of demands, such as network design or routing.

One may consider generalizing our setup to the case when both cost and demand functions are given on arbitrary hypergraphs. Here, a similar situation occurs since few approximation algorithms for Hypergraph Sparsest Cut are known [24], [25], but we are not aware of any results on hypergraph analogues of other graph partitoning objectives studied in this work. What would probably be required in order to tackle these tasks is a new notion of hypergraph conductance, similar in spirit to our generalized conductance. Obtaining approximation algorithms for such a measure would be an interesting direction for future work.

Incorporating our setup into the framework of spectral graph theory is another promising direction. In particular, it is known that the classical conductance is closely related to the second eigenvalue of the Laplacian matrix of a graph. It would be of interest to see whether a similar relationship can be established for generalized conductance and some appropriate generalization of the Laplacian matrix.

7 Appendix↩︎

7.1 Proof of Theorem 5↩︎

References↩︎

---

1. Note, that there are several similar definitions of the conductance, however they are all equivalent up to constant factors.↩︎

2. The subscripts indicate which constants are hidden in the \(\mathcal{O}\)-notation.↩︎

3. Here \(\phi(G)=\min_{S}\frac{c\mathopen{}\left( S,\bar{S} \right)}{\min\mathopen{}\left( \operatorname{vol}(S),\operatorname{vol}(\bar{S}) \right)}\), which differs slightly from the notion of conductance used in this work; the two, however, agree up to a factor of \(2\) and hence are equivalent for the purposes of the above discussion.↩︎

4. We use the word ‘reduction’ since both \(S_1\) and \(S_2\) are obtained via an algorithmic reduction to another combinatorial problem, either Generalized Sparsest Cut (with restrictions) or Generalized \(k\)-Multicut.↩︎

5. In fact the algorithm given below produces a clustering tree which might be non-binary.↩︎