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)

Abstract

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
PublisherSpringer
Pages125-135
Number of pages11
ISBN (Print)978-3-642-19221-0
DOIs
Publication statusPublished - Mar 2011

Publication series

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

Keywords

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

Cite this

Bonsma, P. S., Broersma, H. J., Patel, V., & Pyatkin, A. (2011). The complexity status of problems related to sparsest cuts. In C. S. Iliopoulos, & W. F. Smyth (Eds.), Proceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010 (pp. 125-135). (Lecture Notes in Computer Science; Vol. 6460). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-19222-7_14