Nonuniform graph partitioning with just a little flex

23^rd September 2025, 13:00 ELEC201, 2th Floor Lecture Theater EEE
Neil Olver
LSE

Abstract

In the nonuniform graph partitioning problem, we are given a capacitated graph G on n vertices, and numbers n_1, n_2, ..., n_t summing to n. The goal is to partition the vertices of G into parts S_1, S_2, ..., S_t with |S_i| = n_i for each i, and minimising the capacity of edges crossing between distinct parts. This generalizes, for instance, the well-known graph bisection problem.

In order to obtain positive results, it is necessary to consider a bicriteria approximation, where we allow part sizes to be violated by a multiplicative factor r (i.e., |S_i| 0 (Feldmann and Foscini 2011, Andreev and Raecke 2008). Krauthgamer, Naor, Schwartz and Talwar (2014) showed an O(log n) approximation for the nonuniform problem for any r >= 1, but 1 is a particular barrier to their techniques. We overcome this barrier to give an an O(log n) approximation for any constant r > 0.

(Joint work with Harald Raecke and Stefan Schmid.)