The complexity of finding uniform sparsest cuts in various graph classes

P.S. Bonsma, Haitze J. Broersma, Viresh Patel, A.V. Pyatkin

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Given an undirected graph G=(V,E), the (uniform, unweighted) sparsest cut problem is to find a vertex subset S⊂V minimizing View the MathML source. We show that this problem is NP-complete, and give polynomial time algorithms for various graph classes. In particular, we show that the sparsest cut problem can be solved in linear time for unit interval graphs, and in cubic time for graphs of bounded treewidth. For cactus graphs and outerplanar graphs this can be improved to linear time and quadratic time, respectively. For graphs of clique-width k for which a short decomposition is given, we show that the problem can be solved in time O(n2k+1), where n is the number of vertices in the input graph. We also establish that a running time of the form nO(k) is optimal in this case, assuming that the Exponential Time Hypothesis holds.
Original languageUndefined
Pages (from-to)136-149
Number of pages14
JournalJournal of discrete algorithms
Volume14
DOIs
Publication statusPublished - 2012

Keywords

  • EWI-21075
  • MSC-05C
  • Treewidth
  • Unit interval graph
  • IR-82684
  • Parameterized complexity
  • Clique-width
  • METIS-293160
  • Sparsest cut

Cite this

Bonsma, P.S. ; Broersma, Haitze J. ; Patel, Viresh ; Pyatkin, A.V. / The complexity of finding uniform sparsest cuts in various graph classes. In: Journal of discrete algorithms. 2012 ; Vol. 14. pp. 136-149.
@article{90148c92f4914011851da4833f45cf4d,
title = "The complexity of finding uniform sparsest cuts in various graph classes",
abstract = "Given an undirected graph G=(V,E), the (uniform, unweighted) sparsest cut problem is to find a vertex subset S⊂V minimizing View the MathML source. We show that this problem is NP-complete, and give polynomial time algorithms for various graph classes. In particular, we show that the sparsest cut problem can be solved in linear time for unit interval graphs, and in cubic time for graphs of bounded treewidth. For cactus graphs and outerplanar graphs this can be improved to linear time and quadratic time, respectively. For graphs of clique-width k for which a short decomposition is given, we show that the problem can be solved in time O(n2k+1), where n is the number of vertices in the input graph. We also establish that a running time of the form nO(k) is optimal in this case, assuming that the Exponential Time Hypothesis holds.",
keywords = "EWI-21075, MSC-05C, Treewidth, Unit interval graph, IR-82684, Parameterized complexity, Clique-width, METIS-293160, Sparsest cut",
author = "P.S. Bonsma and Broersma, {Haitze J.} and Viresh Patel and A.V. Pyatkin",
note = "eemcs-eprint-21075",
year = "2012",
doi = "10.1016/j.jda.2011.12.008",
language = "Undefined",
volume = "14",
pages = "136--149",
journal = "Journal of discrete algorithms",
issn = "1570-8667",
publisher = "Elsevier",

}

The complexity of finding uniform sparsest cuts in various graph classes. / Bonsma, P.S.; Broersma, Haitze J.; Patel, Viresh; Pyatkin, A.V.

In: Journal of discrete algorithms, Vol. 14, 2012, p. 136-149.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - The complexity of finding uniform sparsest cuts in various graph classes

AU - Bonsma, P.S.

AU - Broersma, Haitze J.

AU - Patel, Viresh

AU - Pyatkin, A.V.

N1 - eemcs-eprint-21075

PY - 2012

Y1 - 2012

N2 - Given an undirected graph G=(V,E), the (uniform, unweighted) sparsest cut problem is to find a vertex subset S⊂V minimizing View the MathML source. We show that this problem is NP-complete, and give polynomial time algorithms for various graph classes. In particular, we show that the sparsest cut problem can be solved in linear time for unit interval graphs, and in cubic time for graphs of bounded treewidth. For cactus graphs and outerplanar graphs this can be improved to linear time and quadratic time, respectively. For graphs of clique-width k for which a short decomposition is given, we show that the problem can be solved in time O(n2k+1), where n is the number of vertices in the input graph. We also establish that a running time of the form nO(k) is optimal in this case, assuming that the Exponential Time Hypothesis holds.

AB - Given an undirected graph G=(V,E), the (uniform, unweighted) sparsest cut problem is to find a vertex subset S⊂V minimizing View the MathML source. We show that this problem is NP-complete, and give polynomial time algorithms for various graph classes. In particular, we show that the sparsest cut problem can be solved in linear time for unit interval graphs, and in cubic time for graphs of bounded treewidth. For cactus graphs and outerplanar graphs this can be improved to linear time and quadratic time, respectively. For graphs of clique-width k for which a short decomposition is given, we show that the problem can be solved in time O(n2k+1), where n is the number of vertices in the input graph. We also establish that a running time of the form nO(k) is optimal in this case, assuming that the Exponential Time Hypothesis holds.

KW - EWI-21075

KW - MSC-05C

KW - Treewidth

KW - Unit interval graph

KW - IR-82684

KW - Parameterized complexity

KW - Clique-width

KW - METIS-293160

KW - Sparsest cut

U2 - 10.1016/j.jda.2011.12.008

DO - 10.1016/j.jda.2011.12.008

M3 - Article

VL - 14

SP - 136

EP - 149

JO - Journal of discrete algorithms

JF - Journal of discrete algorithms

SN - 1570-8667

ER -