On Computing the Global Minimum Cut in Directed Surface-Embedded Graphs

We present an algorithm to compute the global minimum cut in a restricted class of directed surface-embedded graphs with fixed genus. Specifically, we assume no cycles dual to the minimum cut cross any shortest path more than c times. Under this assumption, our algorithm computes the cut in O(c O(g)n log n) time. Our algorithm is primarily based on a strategy given by Erickson, Fox, and Nayyeri to compute the global minimum cut in undirected surface-embedded graphs. We also show that any algorithm which computes the cut in directed graphs without our restriction cannot rely on the commonly established bound in planar and undirected surface-embedded graphs on the number of times any dual cycle corresponding to the minimum cut crosses any shortest path.