Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.