An improved approximation algorithm for requirement cut

Anupam Gupta, Viswanath Nagarajan, R. Ravi

Research output: Contribution to journalArticlepeer-review


This note presents improved approximation guarantees for the requirement cut problem: given an n-vertex edge-weighted graph G=(V,E), and g groups of vertices X1,...,Xg ⊆ V with each group Xi having a requirement ri between 0 and |Xi|, the goal is to find a minimum cost set of edges whose removal separates each group Xi into at least ri disconnected components. We give a tight Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk·logg) approximation ratio for general graphs, where k=|∪gi=1=1gXi|≤n.

Original languageEnglish (US)
Pages (from-to)322-325
Number of pages4
JournalOperations Research Letters
Issue number4
StatePublished - Jul 2010


  • Approximation algorithms
  • Graph partitioning

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


Dive into the research topics of 'An improved approximation algorithm for requirement cut'. Together they form a unique fingerprint.

Cite this