We study the approximability of multiway partitioning problems, examples of which inlude Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate these problems from the point of view of two possible generalizations: as Min-CSPs, and as Submodular Multiway Partition problems. These two generalizations lead to two natural relaxations that we call respectively the Local Distribution LP, and the Lovasz relaxation. We show that Lovasz relaxation gives an (2-2/k)-approximation submodular multiway partition problem with k terminals, improving a recent 2-approximation. We prove that such an approximation is actually optimal in the following two senses: 1) in the value oracle model, getting better than (2-2/k)-approximation requires exponential number of queries; 2) even for the very special form such as hypergraph multiway cut and node-weighted multiway cut, it is NP Hard to get better than (2-2/k)-approximation assuming the Unique Games Conjecture.

Both our hardness proofs are more general: Assuming the Unique Games Conjecture, we show that the Local Distribution LP gives an optimal approximation for every Min-CSP that includes the Not- Equal predicate. In the value oracle model, we show how the technique of symmetry gap applies to submodular minimization problems, and in particular gives hardness of (2 - 2/k -eps )-approximation for Submodular Multiway Partition. Finally, we show that an integrality gap of the Local Distribution LP implies a symmetry gap for a Min-CSP instance of the same type, which connects the two techniques for proving hardness results.

This is a joint work with Alina Ene and Jan Vondrak