Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion

Eden Chlamtác, Michael Dinitz, Yury Makarychev

Abstract

The Minimum $k$-Union (MkU) problem—finding $k$ sets in a collection whose union is minimized—is a fundamental challenge in combinatorial optimization with deep ties to graph expansion. This paper presents a nearly tight $n^{1/4+\epsilon}$ approximation algorithm for MkU, significantly improving upon the previous $O(\sqrt{n})$ bound. By framing MkU as the Small Set Bipartite Vertex Expansion (SSBVE) problem, the authors utilize a refined log-density framework and a novel asymmetric pruning technique. Complementing this algorithmic result, the paper establishes a matching $n^{1/4}$ lower bound based on the "Dense versus Random" conjecture and demonstrates substantial integrality gaps for standard Linear Programming (LP) and Semidefinite Programming (SDP) relaxations.

Introduction

In the Minimum $k$-Union (MkU) problem, one is given a collection of $n$ sets and must select exactly $k$ of them such that the size of their union is minimized. While it may appear to be a simple variation of the well-known Maximum Coverage problem, MkU is significantly more difficult to approximate. Maximum Coverage enjoys a constant-factor approximation of $(1 - 1/e)$, but MkU belongs to a class of problems related to the Densest $k$-Subgraph (DkS) and Smallest $m$-Edge Subgraph, where gaps between upper and lower bounds have persisted for decades.

The authors demonstrate that MkU is equivalent to finding the "least expanding" set of $k$ nodes in a bipartite graph, a problem they term Small Set Bipartite Vertex Expansion (SSBVE). Prior to this work, the state-of-the-art approximation stood at $O(\sqrt{n})$. This paper bridges the gap by identifying $n^{1/4}$ as the natural complexity threshold for the problem.

Algorithmic Framework: Log-Density and Asymmetric Pruning

The authors' approach is rooted in the "log-density" framework, an algorithmic strategy designed to navigate the combinatorial complexity of dense subgraph problems. The algorithm proceeds through three primary phases:

  1. Planted Model Analysis: The problem is first analyzed through the lens of a "planted" instance—distinguishing between a purely random graph and one containing a hidden, low-expansion solution. This helps establish the theoretical limits of what a polynomial-time algorithm can detect.
  2. Caterpillar Construction: The algorithm constructs a solution inductively using a "caterpillar" structure. This involves a sequence of "backbone" steps, which involve taking neighborhoods of sets, and "hair" steps, which involve intersecting the current set with the neighborhood of a specifically chosen node.
  3. Asymmetric Pruning: A significant technical contribution of this work is the introduction of asymmetric pruning. In bipartite expansion, a small number of high-degree nodes on one side of the graph can disproportionately inflate the union size. The authors developed a pruning mechanism to isolate and ignore these "bad" nodes, allowing the algorithm to maintain a low expansion ratio throughout its inductive steps.

Hardness and Integrality Gaps

To justify the $n^{1/4}$ approximation factor, the paper provides evidence that this bound is likely optimal. By extending the "Dense versus Random" conjecture from simple graphs to hypergraphs, the authors show that any algorithm achieving an approximation better than $n^{1/4}$ would effectively refute a long-standing complexity conjecture.

Furthermore, the paper investigates why traditional convex relaxations fail for MkU:

  • Sherali-Adams Hierarchy: Even after a super-constant number of rounds, the integrality gap for Linear Programming remains $\Omega(n^{1/4})$.
  • Semidefinite Programming (SDP): The natural SDP relaxation performs even worse, exhibiting a gap of $\tilde{\Omega}(\sqrt{n})$.

These results suggest that the $n^{1/4}$ barrier is not merely a limitation of current algorithms but is inherent to the geometry of the problem's relaxation space.

Conclusion

This work provides a comprehensive characterization of the Small Set Bipartite Vertex Expansion problem. By delivering an $O(n^{1/4+\epsilon})$ approximation and a matching conditional lower bound, the authors establish $n^{1/4}$ as the tight complexity bound for general hypergraphs. While this resolves the general case, future research is required for restricted settings, such as hypergraphs with bounded edge sizes, where the current approximation ratios remain far from the theoretical optimum.

Summary updated

BibTeX
@inproceedings{chlamtac2017minimizing,
  author = {Eden Chlamtác and Michael Dinitz and Yury Makarychev},
  title = {{Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion}},
  booktitle = {SODA},
  year = {2017},
  url = {https://openreview.net/forum?id=aYwAixH5dxA},
}
Figure