<p>Most problems about cutting graphs into roughly equal parts such as <a href="https://en.wikipedia.org/wiki/Cut_(graph_theory)" rel="nofollow noreferrer">Sparsest cut</a>, <a href="https://en.wikipedia.org/wiki/Graph_partition" rel="nofollow noreferrer">Graph partition</a>, <a href="https://pages.cs.wisc.edu/%7Eshuchi/courses/880-S07/scribe-notes/lecture18.pdf" rel="nofollow noreferrer">Balanced Cut</a>, etc are based on minimizing the size of an edge cut. Even if all of those problems are NP-Hard, good approximations exist and are quite efficient in practice. Are there good equivalents for vertex cuts or maybe a way to modify a graph <span class="math-container">$G$</span> into <span class="math-container">$G'$</span> so a balanced edge cut for <span class="math-container">$G'$</span> becomes a balanced vertex cut for <span class="math-container">$G$</span>?</p>
<p>Tricks like representing a vertex as a pair of vertices with an edge between them (the construction to reduce the max-flow/min-cut vertex theorem to the edge version) don't seem to work in this case as everything is undirected.</p>
<p>I am aware that it is possible to extract a vertex cut from an edge cut efficiently, but this only gives a somewhat loose heuristic.</p>

CC BY-SA 4.0
2022-08-15T16:18:51.167Z
Searching for "small vertex separator" yields e.g. https://doi.org/10.1007/s00453-018-0490-x , which seems to be an example of what you're looking for.  Can you make sure you've looked through existing literature, and edit your post to explain what you've found and what you are looking for that you haven't found?
Neal Young
CC BY-SA 4.0
2022-08-15T17:24:42.110Z
Another nice paper in the area is https://epubs.siam.org/doi/abs/10.1137/05064299X
Laakeri
CC BY-SA 4.0
2022-08-15T19:24:32.173Z
Thank you! I guess I was googling with the wrong keywords (like sparsest vertex cut)! Do you know if they are any implementations of such algorithms available?
Julien Codsi
CC BY-SA 4.0
2022-08-15T19:35:47.013Z
https://arxiv.org/abs/2205.13202 discusses implementations of separator algorithms.
Chandra Chekuri
CC BY-SA 4.0
2022-08-15T21:36:21.580Z
Metis (https://github.com/KarypisLab/METIS) is one practical implementation for computing balanced separators.  Including vertex separators (e.g. https://networkx-metis.readthedocs.io/en/latest/reference/generated/nxmetis.vertex_separator.html)
Neal Young
<ds.algorithms><graph-theory><graph-algorithms><approximation-algorithms>
Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?
Julien Codsi
# Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?

(Asked by: username_0 on 2022-08-15)

Most problems about cutting graphs into roughly equal parts such as [Sparsest cut](https://en.wikipedia.org/wiki/Cut_(graph_theory)), [Graph partition](https://en.wikipedia.org/wiki/Graph_partition), [Balanced Cut](https://pages.cs.wisc.edu/%7Eshuchi/courses/880-S07/scribe-notes/lecture18.pdf), etc are based on minimizing the size of an edge cut. Even if all of those problems are NP-Hard, good approximations exist and are quite efficient in practice. Are there good equivalents for vertex cuts or maybe a way to modify a graph $G$ into $G'$ so a balanced edge cut for $G'$ becomes a balanced vertex cut for $G$?

Tricks like representing a vertex as a pair of vertices with an edge between them (the construction to reduce the max-flow/min-cut vertex theorem to the edge version) don't seem to work in this case as everything is undirected.

I am aware that it is possible to extract a vertex cut from an edge cut efficiently, but this only gives a somewhat loose heuristic.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, approximation-algorithms
> **Comments:**
> **username_1**: Searching for "small vertex separator" yields e.g. https://doi.org/10.1007/s00453-018-0490-x , which seems to be an example of what you're looking for.  Can you make sure you've looked through existing literature, and edit your post to explain what you've found and what you are looking for that you haven't found?  
> **username_2**: Another nice paper in the area is https://epubs.siam.org/doi/abs/10.1137/05064299X  
> **username_0**: Thank you! I guess I was googling with the wrong keywords (like sparsest vertex cut)! Do you know if they are any implementations of such algorithms available?  
> **username_3**: https://arxiv.org/abs/2205.13202 discusses implementations of separator algorithms.  
> **username_1**: Metis (https://github.com/KarypisLab/METIS) is one practical implementation for computing balanced separators.  Including vertex separators (e.g. https://networkx-metis.readthedocs.io/en/latest/reference/generated/nxmetis.vertex_separator.html)  

---

## 0 answers

