Submodular $k$-Partition is the following problem: given a submodular set function $f:2^V \rightarrow \mathbb{R}$ and an integer $k$, find a partition of $V$ into $k$ non-empty parts $V_1,V_2,\ldots,V_k$ to minimize $\sum_{i=1}^k f(V_i)$. Several interesting problems such as Graph $k$-Cut, Hypergraph $k$-Cut and Hypergraph $k$-Partition are special cases. Submodular $k$-Partition admits a polynomial-time algorithm for $k=2,3$ and when $f$ is symmetric also for $k=4$. The complexity is open for $k=4$ and when $f$ is symmetric for $k=5$.

In recent work, motivated by this problem, we examined the complexity of Hypergraph $k$-Cut which only recently admitted a randomized polynomial-time algorithm. We obtained a deterministic polynomial-time algorithm for Hypergraph $k$-Cut as well as new insights in to Graph $k$-Cut. The ideas also led to a polynomial-time algorithm for Min-Max Symmetric Submodular $k$-Partition for any fixed $k$.

The talk will discuss these results with the goal of highlighting the open problem of resolving the complexity of Submodular $k$-Partition.

Based on joint work with Karthik Chandrasekharan