p-norm multiway cut

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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(log2 n)-approximation for all p ≥ 1. We also show an integrality gap of Ω(k1−1/p) for a natural convex program and an O(k1−1/p−ϵ)-inapproximability for any constant ϵ > 0 assuming the small set expansion hypothesis.

Original languageEnglish (US)
Title of host publication29th Annual European Symposium on Algorithms, ESA 2021
EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772044
StatePublished - Sep 1 2021
Event29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal
Duration: Sep 6 2021Sep 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference29th Annual European Symposium on Algorithms, ESA 2021
CityVitual, Lisbon


  • Approximation algorithms
  • Multiway cut

ASJC Scopus subject areas

  • Software

Cite this