Approximation Algorithms for Norm Multiway Cut

Abstract

We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph $G$ into $k$ parts so as to separate $k$ given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced ${\ell }_p$-norm Multiway, a generalization of the problem, in which the goal is to minimize the ${\ell }_p$ norm of the edge boundaries of $k$ parts. We provide an $O({\log }^{1/2}n{\log }^{1/2+1/p}k)$ approximation algorithm for this problem, improving upon the approximation guarantee of $O({\log }^{3/2}n{\log }^{1/2}k)$ due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an $O({\log }^{1/2}n{\log }^{7/2}k)$ approximation algorithm with a weaker oracle and an $O({\log }^{1/2}n{\log }^{5/2}k)$ approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no $n^{1/4-\epsilon }$ approximation algorithm for every $\epsilon >0$ assuming the Hypergraph Dense-vs-Random Conjecture.

25 pages, ESA 2023