Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.