ℓ_p-norm Multiway Cut

2021/06/28 by Karthekeyan Chandrasekaran, Chandrasekaran, Karthekeyan, Weihang Wang +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.2106.14840

arxiv created 2021/06/28 · arxiv updated 2021/06/29

Abstract

We introduce and study ℓ_p-norm-multiway-cut: the input here is an undirected graph with non-negative edge weights along with k terminals and the goal is to find a partition of the vertex set into k parts each containing exactly one terminal so as to minimize the ℓ_p-norm of the cut values of the parts. This is a unified generalization of min-sum multiway cut (when p=1) and min-max multiway cut (when p=∞), both of which are well-studied classic problems in the graph partitioning literature. We show that ℓ_p-norm-multiway-cut is NP-hard for constant number of terminals and is NP-hard in planar graphs. On the algorithmic side, we design an O(log² n)-approximation for all p≥ 1. We also show an integrality gap of Ω(k^1-1/p) for a natural convex program and an O(k^1-1/p-ε)-inapproximability for any constant ε>0 assuming the small set expansion hypothesis.

Related

• Approximation Algorithms for Norm Multiway Cut
• Improving the Integrality Gap for Multiway Cut
• Computing multiway cut within the given excess over the largest minimum isolating cut
• On Multiway Cut parameterized above lower bounds
• Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems