Min–Max Partitioning of Hypergraphs and Symmetric Submodular Functions

We consider the complexity of minmax partitioning of graphs, hypergraphs and (symmetric) submodular functions. Our main result is an algorithm for the problem of partitioning the ground set of a given symmetric submodular function f: 2 ^V→ R into k non-empty parts V₁, V₂, … , V_k to minimize maxi=1kf(Vi) . Our algorithm runs in nO(k2)T time, where n= | V| and T is the time to evaluate f on a given set; hence, this yields a polynomial time algorithm for any fixed k in the evaluation oracle model. As an immediate corollary, for any fixed k, there is a polynomial-time algorithm for the problem of partitioning a given hypergraph H= (V, E) into k non-empty parts to minimize the maximum capacity of the parts. The complexity of this problem, termed Minmax-Hypergraph- k -Part, was raised by Lawler in 1973 (Networks 3:275–285, 1973). In contrast to our positive result, the reduction in Chekuri and Li (Theory Comput 16(14):1–8, 2020) implies that when k is part of the input, Minmax-Hypergraph- k -Part is hard to approximate to within an almost polynomial factor under the Exponential Time Hypothesis (ETH).