The complexity status of problems related to sparsest cuts

P.S. Bonsma, Haitze J. Broersma, Viresh Patel, Artem Pyatkin

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)


Given an undirected graph G = (V,E) with a capacity function w on the edges, the sparsest cut problem is to find a vertex subset S ⊂ V minimizing ∑  e ∈ E(S,V ∖ S) w(e)/(|S||V ∖ S|). This problem is NP-hard. The proof can be found in [16]. In the case of unit capacities (i. e. if w(e) = 1 for every e ∈ E) the problem is to minimize |E(S,V ∖ S)|/(|S||V ∖ S|) over all subsets S ⊂ V. While this variant of the sparsest cut problem is often assumed to be NP-hard, this note contains the first proof of this fact. We also prove that the problem is polynomially solvable for graphs of bounded treewidth.
Original languageUndefined
Title of host publicationProceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010
EditorsCostas S. Iliopoulos, William F. Smyth
Place of PublicationBerlin, Heidelberg
Number of pages11
ISBN (Print)978-3-642-19221-0
Publication statusPublished - Mar 2011
Event21st International Workshop on Combinatorial Algorithms, IWOCA 2010 - London, United Kingdom
Duration: 26 Jul 201028 Jul 2010
Conference number: 21

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International Workshop on Combinatorial Algorithms, IWOCA 2010
Abbreviated titleIWOCA 2010
Country/TerritoryUnited Kingdom


  • IR-79523
  • METIS-285237
  • NP-hardness
  • MSSC
  • EWI-21344
  • Sparsest cut
  • densest cut
  • MSC-05C
  • bounded treewidth

Cite this