<p>The (uniform) directed sparsest cut problem asks for a cut $(S,\bar{S})$ in a directed graph $G=(V,E)$ which minimize the ratio $\frac{\delta_{out}(S) }{|S||\bar{S}|}$, where $\delta_{out}$ is the total capacity of edges coming out from $S$. The best approximation ratio for the problem is $O(\sqrt{\log n})$ via the paper <em>$O(\sqrt{\log n})$ approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems</em>.</p>

<p>The undirected version of the problem on planar graphs have a factor two approximation algorithm:  <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=365709&amp;tag=1">Finding separator cuts in planar graphs within twice the optimal</a> !
Does anybody aware of a similar result for directed sparsest cut on planar graphs ? Can we apply the same technique for the undirected version to get a constant ratio?</p>

CC BY-SA 4.0
2018-07-14T03:22:02.983Z
The problem is open even now as far as I know.
Chandra Chekuri
CC BY-SA 4.0
2023-05-06T12:09:17.877Z
It seems to me that this paper: https://arxiv.org/abs/2105.15187 provides an answer.
Matthieu Latapy
<ds.algorithms><reference-request><graph-theory><planar-graphs>
Directed Sparsest Cut on Planar Graphs?
Thang Dinh
# Directed Sparsest Cut on Planar Graphs?

(Asked by: username_0 on 2011-08-02)

The (uniform) directed sparsest cut problem asks for a cut $(S,\bar{S})$ in a directed graph $G=(V,E)$ which minimize the ratio $\frac{\delta\_{out}(S) }{|S||\bar{S}|}$, where $\delta\_{out}$ is the total capacity of edges coming out from $S$. The best approximation ratio for the problem is $O(\sqrt{\log n})$ via the paper *$O(\sqrt{\log n})$ approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems*.

The undirected version of the problem on planar graphs have a factor two approximation algorithm: [Finding separator cuts in planar graphs within twice the optimal](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=365709&tag=1) !
Does anybody aware of a similar result for directed sparsest cut on planar graphs ? Can we apply the same technique for the undirected version to get a constant ratio?

**Tags:** ds.algorithms, reference-request, graph-theory, planar-graphs

> **Comments:**
> **username_1**: The problem is open even now as far as I know.  
> **username_2**: It seems to me that this paper: https://arxiv.org/abs/2105.15187 provides an answer.  

---

## 0 answers

