TL;DR
This paper provides a nearly tight $n^{1/4+\epsilon}$ approximation algorithm for the Minimum $k$-Union (MkU) problem, which asks to pick $k$ sets whose union is as small as possible. The authors show that this bound is likely optimal by proving a matching lower bound based on plausible complexity conjectures and demonstrating significant integrality gaps for standard LP and SDP relaxations.
What Problem Does This Paper Address?
The authors study the Minimum $k$-Union (MkU) problem: given a collection of $n$ sets, choose exactly $k$ of them such that the size of their union is minimized.
If this sounds familiar, it’s because it is the "minimization" version of the famous Maximum Coverage problem. However, while Maximum Coverage is easy to approximate within a factor of $(1 - 1/e)$, MkU is significantly harder. It can be viewed as finding the "least expanding" set of $k$ nodes in a bipartite graph—a problem the authors call Small Set Bipartite Vertex Expansion (SSBVE).
Before this paper, the best-known approximation was $O(\sqrt{n})$. The challenge lies in the fact that MkU is a natural hypergraph extension of the Smallest $m$-Edge Subgraph problem, which is closely related to the notoriously difficult Densest $k$-Subgraph (DkS) problem. The gap between the best algorithms and known hardness results for these problems has been a long-standing headache in theoretical computer science.
Methods
The authors employ the "log-density" framework, a powerful algorithmic strategy originally developed for the Densest $k$-Subgraph problem. The approach follows three main steps:
- Random vs. Planted Models: They first analyze the problem in a "planted" setting—distinguishing a purely random graph from one where a small, dense solution has been hidden.
- Caterpillar Construction: They design an algorithm that inductively builds a solution using a "caterpillar" structure. This involves a sequence of "backbone" steps (taking neighborhoods) and "hair" steps (intersecting the current set with the neighborhood of a "guessed" node).
- Asymmetric Pruning: A key technical innovation is a new pruning technique. In bipartite graphs, a few "bad" nodes on one side can disproportionately increase the neighborhood size. The authors develop a way to isolate and ignore these nodes to maintain a small expansion ratio throughout the inductive process.
To prove hardness, they extend the "Dense versus Random" conjecture from graphs to hypergraphs and show that any algorithm better than $n^{1/4}$ would break this conjecture.
Datasets
As a theoretical paper, it does not use empirical datasets. Instead, it relies on:
- Random Bipartite Graphs ($G_{n,p}$): Used to establish baseline expansion properties.
- Planted Models: Specifically constructed instances where a small set with an unusually small union is "planted" into a random set system to test the limits of approximation.
Key Insights and Ideas
- Equivalence to SSBVE: By framing MkU as a bipartite vertex expansion problem, the authors can leverage graph-theoretic tools that weren't obvious in the set-system formulation.
- The $n^{1/4}$ Barrier: The paper identifies $n^{1/4}$ as the natural "threshold" for this problem. This comes from the log-density gap: in a random instance, the best $k$-set has a union of a certain size, while in a planted instance, it's significantly smaller. The ratio between these two is roughly $n^{1/4}$.
- LP/SDP Failures: The authors show that standard convex relaxations (Linear Programming and Semidefinite Programming) are particularly weak here. Even after many rounds of the "Sherali-Adams" hierarchy (a method to strengthen LPs), the gap remains $\Omega(n^{1/4})$. The SDP relaxation performs even worse, with a gap of $\tilde{\Omega}(\sqrt{n})$.
Key Results
- Upper Bound: An $O(n^{1/4+\epsilon})$ approximation algorithm for SSBVE/MkU for any constant $\epsilon > 0$. This is a significant improvement over the previous $O(\sqrt{n})$ result.
- Conditional Hardness: They show that an $O(n^{1/4})$ approximation is likely the best possible, assuming an extension of the "Dense versus Random" conjecture for hypergraphs.
- Integrality Gaps:
- Sherali-Adams: A gap of $n^{1/4-O(\epsilon)}$ after a super-constant number of rounds.
- SDP: A gap of $\tilde{\Omega}(\sqrt{n})$ for the natural relaxation.
- General SSVE: They provide the first non-trivial bicriteria approximation for the more general (non-bipartite) Small Set Vertex Expansion problem, achieving an $\tilde{O}(\sqrt{n})$ ratio.
Limitations and Future Work
The main limitation is that the $n^{1/4}$ bound applies to general hypergraphs (where sets can be any size). The authors note that for hypergraphs with bounded edge sizes (e.g., every set has exactly 3 elements), the current best approximation is still far from the predicted lower bound.
Future work remains in closing the gap for these restricted cases and exploring whether new techniques—beyond the log-density framework—can bypass the $n^{1/4}$ barrier for specific graph topologies.
Summary updated