Abstract
Given an undirected graph G = (V,E) with a capacity function \(w : E \longrightarrow \mathbb{Z}^+\) 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering. Journal of Machine Learning 75, 245–248 (2009)
Aloise, D., Hansen, P.: On the complexity of minimum sum-of-squares clustering. Cahiers du GERAD, G–2007–50 (2007), http://www.gerad.ca
Ambühl, C., Mastrolilli, M., Svensson, O.: Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling. In: FOCS, pp. 329–337 (2007)
Arora, S., Hazan, E., Kale, S.: \(O(\sqrt{\log n})\) Approximation to SPARSEST CUT in \(\tilde{O}(n^2)\) Time. SIAM J. Comput. 39(5), 1748–1771 (2010)
Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. In: STOC, pp. 222–231 (2004)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996)
Bodlaender, H.L.: Treewidth: algorithmic techniques and results. In: Privara, I., Ružička, P. (eds.) MFCS 1997. LNCS, vol. 1295, pp. 19–36. Springer, Heidelberg (1997)
Bonsma, P.: Sparsest cuts and concurrent flows in product graphs. Discrete Applied Mathematics 136(2-3), 173–182 (2004)
Bonsma, P.: Linear time algorithms for finding sparsest cuts in various graph classes. In: CS 2006, Prague. Electronic Notes in Discrete Mathematics, vol. 28, pp. 265–272 (2007)
Chlamtac, E., Krauthgamer, R., Raghavendra, P.: Approximating sparsest cuts in graphs of bounded treewidth. arXiv:1006.3970v2 [cs.Ds] (June 23, 2010)
Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol. B, pp. 193–242. Elsevier, Amsterdam (1990)
Drineas, P., Frieze, A., Kannan, R., Vempala, S., Vinay, V.: Clustering large graphs via the singular value decomposition. Journal of Machine Learning 56, 9–33 (2004)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some Simplified NP-Complete Graph Problems. Theoretical Computer Science 1, 237–267 (1976)
Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787–832 (1999)
Matula, D.W., Shahrokhi, F.: Sparsest cuts and bottlenecks in graphs. Discrete Applied Mathematics 27, 113–123 (1990)
Moret, B., Shapiro, H.: Algorithms from P to NP. Benjamin/Cummings (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bonsma, P., Broersma, H., Patel, V., Pyatkin, A. (2011). The Complexity Status of Problems Related to Sparsest Cuts. In: Iliopoulos, C.S., Smyth, W.F. (eds) Combinatorial Algorithms. IWOCA 2010. Lecture Notes in Computer Science, vol 6460. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19222-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-19222-7_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19221-0
Online ISBN: 978-3-642-19222-7
eBook Packages: Computer ScienceComputer Science (R0)