Spectral Graph Theory Without a Spectrum II: Partitioning Hypergraphs via Network Flows

Antares Chen, University of Chicago


Last time, we discussed a non-linear and non-differentiable Laplacian operator for hypergraphs in which aspects of spectral graph theory still generalize to the hypergraph setting. Building on these tools, we discuss a primal-dual approximation algorithm for a specific class of hypergraph partitioning problems called “minimum ratio-cut”. To do this, we construct a family of local, convex relaxations of the minimum ratio-cut problem, and compose dual solutions using “cut-matching games” to certify lower bounds on the minimum ratio-cut objective. This approach leads to the first $O(\log n)$-approximation for hypergraph sparsest cut that runs in almost-linear time.

Joint work with Konstantinos Ameranis, Lorenzo Orecchia, and Erasmo Tani.

Nov 30, 2022 12:30 PM — 1:30 PM
Theory Lunch
JCL 298

Join via Zoom