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
Bonsma, P.S. ; Broersma, Haitze J. ; Patel, Viresh ; Pyatkin, Artem. / The complexity status of problems related to sparsest cuts. Proceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010. editor / Costas S. Iliopoulos ; William F. Smyth. Berlin, Heidelberg : Springer, 2011. pp. 125-135 (Lecture Notes in Computer Science).
@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",
year = "2011",
month = "3",
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. 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; Pyatkin, Artem.

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 proceedingConference contributionAcademicpeer-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 - 10.1007/978-3-642-19222-7_14

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

ER -

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