Graph Partitioning with Demands: Generalized Conductance and its Applications

Technical Summary: Graph Partitioning with Demands: Generalized Conductance and its Applications

Problem Definition
This work addresses graph partitioning problems under a general demand model. The input is a graph $G = (V, E, c, w)$, where $c: E \to \mathbb{N}$ is a capacity function (edge costs) and $w: V \times V \to \mathbb{N}$ is a demand function representing the importance of separating vertex pairs.

The central problem introduced is the Generalized Conductance Problem. The goal is to find a cut $(S, \bar{S})$ that minimizes the quantity:
$$\psi_w(S) = \frac{c(S, \bar{S})}{w(S, V) \cdot w(\bar{S}, V)}$$
where $c(S, \bar{S})$ is the cost of edges crossing the cut, and $w(X, V) = w(X) + w(X, \bar{X})$ represents the total demand incident to set $X$ (both internal and crossing).

The authors note that while the classic Sparsest Cut (minimizing $c(S, \bar{S}) / w(S, \bar{S})$) is well-studied, it fails to capture "balance" in general demand settings. For instance, a perfectly balanced cut with zero crossing demand yields an infinite Sparsest Cut value, whereas the Generalized Conductance remains finite and meaningful. This metric is crucial for applications requiring balanced partitions, such as divide-and-conquer strategies.

Methodology and Algorithmic Framework
The paper proposes a two-way reduction strategy to solve the Generalized Conductance Problem, resulting in an $O(\log n)$-approximation for general graphs. The algorithm operates by computing two candidate cuts, $S_1$ and $S_2$, and returning the one with the better objective value. The choice depends on the magnitude of the demand crossing the optimal cut, $w(S^*, \bar{S}^*)$.

1. Case 1: Small Crossing Demand ($w(S^*, \bar{S}^*) \le w(V)/3$)

   • Reduction: The problem is reduced to a Generalized Sparsest $K$-Bounded Cut problem.
   • Technique: An auxiliary graph $G'$ is constructed by adding a universal vertex $r$ with zero-cost edges to all original vertices. The demand from $r$ to any vertex $u$ is set to the total demand incident to $u$ in the original graph.
   • Constraint: The algorithm solves for a cut in $G'$ that minimizes sparsity subject to an upper bound $K = \frac{4}{3}w(V)$ on the total demand cut. This constraint ensures the trivial cut ($S=V$) is not selected and forces a balanced partition.
   • Subroutine: This step utilizes an $\alpha$-approximation for the Sparsest $K$-Bounded Cut.

2. Case 2: Large Crossing Demand ($w(S^*, \bar{S}^*) \ge w(V)/3$)

   • Reduction: The problem is reduced to the Generalized $k$-Multicut problem followed by a Max-Cut step.
   • Technique: First, a $k$-Multicut is computed with $k = w(V)/3$ to separate a significant portion of the demand, yielding a set of connected components.
   • Refinement: These components form the vertices of a new complete graph $R$, where edge weights represent the demand between components. A Max-Cut is computed on $R$ (using a greedy 2-approximation) to split the components into two groups.
   • Subroutine: This step utilizes a $\beta$-approximation for Generalized $k$-Multicut.

Solving the Subproblems
To achieve the final approximation guarantees, the paper employs Räcke's cut-sparsifier tree decomposition.

• The general graph is embedded into a probability distribution over a polynomial number of trees.
• This embedding preserves cut values within an $O(\log n)$ distortion in expectation.
• The algorithm solves the subproblems (Sparsest $K$-Bounded Cut and $k$-Multicut) optimally on each tree in the support of the distribution.
• On trees, these problems are solvable in polynomial time (often linear) by considering single-edge cuts.
• The best solution among all trees is selected, yielding the $O(\log n)$ approximation for general graphs.

Key Results
The paper establishes the following approximation guarantees:

1. Generalized Conductance:

   • General Graphs: $O(\log n)$-approximation.
   • Trees: $O(1)$-approximation (exact solvability).
   • Multiplicative Demands: If $w(u, v) = \pi(u)\pi(v)$, the guarantee improves to $O(\sqrt{\log n})$. This is achieved by reducing the problem to the Min-Ratio Vertex Cut problem.

2. Graph Partitioning with Demands:

   • Goal: Find a minimum-cost edge set $C$ such that every connected component $H$ in $G \setminus C$ satisfies $w(H) \le \rho \cdot w(V)$.
   • Result: An $O(\log n)$-bicriteria approximation is obtained. The algorithm returns a cut with cost $O(\log n) \cdot \text{OPT}$ while ensuring component demands are at most $\eta \cdot w(V)$ (where $\rho < \eta < 1$).
   • Multiplicative/Trees: Guarantees improve to $O(\sqrt{\log n})$ and $O(1)$ respectively.

3. Hierarchical Clustering with Demands:

   • Goal: Minimize Dasgupta's objective (sum of cut costs weighted by cluster demand) by recursively partitioning the graph.
   • Result: By iteratively applying the Graph Partitioning algorithm, the paper derives an $O(\log n)$-approximation for general graphs, $O(1)$ for trees, and $O(\sqrt{\log n})$ for multiplicative demands.

Significance and Claims
The authors position Generalized Conductance as a robust algorithmic primitive, analogous to the role of Sparsest Cut in classical divide-and-conquer methods. The primary contribution is the initiation of the study of this specific parameter, which bridges the gap between standard sparsity measures and the need for balanced partitions in general demand settings.

The work demonstrates that despite the complexity of general demands, the problem remains tractable with logarithmic approximation factors. The paper explicitly claims that these results extend to downstream tasks like hierarchical clustering, providing the first non-trivial approximation guarantees for these problems under general demand models. The authors note that for multiplicative demands, the results align with the state-of-the-art for Uniform Sparsest Cut, and for trees, they achieve constant-factor approximations.

The paper concludes by suggesting future directions, including extending the framework to hypergraphs (requiring a new notion of hypergraph conductance) and exploring connections to spectral graph theory, specifically whether a generalized Laplacian can relate to generalized conductance similar to the classical Cheeger inequality.