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.

PDF
Restricted to UT campus only: Request a copy
218Kb

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
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP) Formal Methods and Tools (FMT)
Link to this item:	http://purl.utwente.nl/publications/79523
Official URL:	http://dx.doi.org/10.1007/978-3-642-19222-7_14
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page