The complexity status of problems related to sparsest cuts

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

doi:10.1007/978-3-642-19222-7_14

The complexity status of problems related to sparsest cuts

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	Undefined
Title of host publication	Proceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010
Editors	Costas S. Iliopoulos, William F. Smyth
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	125-135
Number of pages	11
ISBN (Print)	978-3-642-19221-0
DOIs	https://doi.org/10.1007/978-3-642-19222-7_14
Publication status	Published - Mar 2011
Event	21st International Workshop on Combinatorial Algorithms, IWOCA 2010 - London, United Kingdom Duration: 26 Jul 2010 → 28 Jul 2010 Conference number: 21

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	6460
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Workshop on Combinatorial Algorithms, IWOCA 2010
Abbreviated title	IWOCA 2010
Country/Territory	United Kingdom
City	London
Period	26/07/10 → 28/07/10

Keywords

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

Access to Document

10.1007/978-3-642-19222-7_14

http://eprints.eemcs.utwente.nl/secure2/21344/01/fulltext-15.pdf

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). Springer. https://doi.org/10.1007/978-3-642-19222-7_14

@inproceedings{15f97c0b3a454b639bab509f4d1a7bc0,

title = "The complexity status of problems related to sparsest cuts",

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.",

keywords = "IR-79523, METIS-285237, NP-hardness, MSSC, EWI-21344, Sparsest cut, densest cut, MSC-05C, bounded treewidth",

author = "P.S. Bonsma and Broersma, {Haitze J.} and Viresh Patel and Artem Pyatkin",

note = "10.1007/978-3-642-19222-7_14 ; 21st International Workshop on Combinatorial Algorithms, IWOCA 2010 ; Conference date: 26-07-2010 Through 28-07-2010",

year = "2011",

month = mar,

doi = "10.1007/978-3-642-19222-7_14",

language = "Undefined",

isbn = "978-3-642-19221-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "125--135",

editor = "Iliopoulos, {Costas S.} and Smyth, {William F.}",

booktitle = "Proceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010",

}

Bonsma, PS, Broersma, HJ, Patel, V & Pyatkin, A 2011, The complexity status of problems related to sparsest cuts. in CS Iliopoulos & WF Smyth (eds), Proceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010. Lecture Notes in Computer Science, vol. 6460, Springer, Berlin, Heidelberg, pp. 125-135, 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, London, United Kingdom, 26/07/10. https://doi.org/10.1007/978-3-642-19222-7_14

The complexity status of problems related to sparsest cuts. / Bonsma, P.S.; Broersma, Haitze J.; Patel, Viresh et al.
Proceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010. ed. / Costas S. Iliopoulos; William F. Smyth. Berlin, Heidelberg: Springer, 2011. p. 125-135 (Lecture Notes in Computer Science; Vol. 6460).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The complexity status of problems related to sparsest cuts

AU - Bonsma, P.S.

AU - Broersma, Haitze J.

AU - Patel, Viresh

AU - Pyatkin, Artem

N1 - Conference code: 21

PY - 2011/3

Y1 - 2011/3

N2 - 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.

AB - 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.

KW - IR-79523

KW - METIS-285237

KW - NP-hardness

KW - MSSC

KW - EWI-21344

KW - Sparsest cut

KW - densest cut

KW - MSC-05C

KW - bounded treewidth

U2 - 10.1007/978-3-642-19222-7_14

DO - 10.1007/978-3-642-19222-7_14

M3 - Conference contribution

SN - 978-3-642-19221-0

T3 - Lecture Notes in Computer Science

SP - 125

EP - 135

BT - Proceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010

A2 - Iliopoulos, Costas S.

A2 - Smyth, William F.

PB - Springer

CY - Berlin, Heidelberg

T2 - 21st International Workshop on Combinatorial Algorithms, IWOCA 2010

Y2 - 26 July 2010 through 28 July 2010

ER -