The complexity status of problems related to sparsest cuts


Bonsma, Paul and Broersma, Hajo and Patel, Viresh and Pyatkin, Artem (2011) The complexity status of problems related to sparsest cuts. In: 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, 26-28 July 2010, London, UK (pp. pp. 125-135).

[img] PDF
Restricted to UT campus only
: Request a copy
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.
Item Type:Conference or Workshop Item
Copyright:© 2011 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page