### Abstract

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

Publication status | Published - Mar 2011 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 6460 |

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

*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

}

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

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