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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.