Family 117Theoretical computer scienceLeanNot yet digested
Uniform sparsest cut: hardness and semidefinite gaps
Proves that approximating Uniform Sparsest Cut within any fixed constant factor is NP-hard, even with nonnegative rational capacities and unit demands. The Goemans–Linial semidefinite relaxation also has integrality gaps of order at least , approaching the square-root-logarithmic upper bound.
Manuscripts in this family · 2
Constant-factor hardness of uniform sparsest cut
Sep 24, 2026·Constant-factor-hardness-of-uniform-sparsest-cut-September-24-2026.pdf
We prove that, for every fixed C > 1, approximating Uniform Sparsest Cut within factor C is NP-hard. The output graphs have nonnegative rational capacities and unit demand between every pair of distinct vertices.
Near-square-root logarithmic integrality gaps for uniform sparsest cut
Sep 24, 2026·Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut-September-24-2026.pdfLean
We construct uniform sparsest-cut instances whose Goemans–Linial semidefinite integrality gap is at least along a sequence . The demand is one between every pair of distinct vertices, and the capacities are nonnegative real numbers. This matches the Arora–Rao–Vazirani upper bound up to a power of .