Counting and Sampling Minimum Cuts in Genus g Graphs

Let G be a directed graph with n vertices embedded on an orientable surface of genus g with two designated vertices s and t. We show that counting the minimum (s, t)-cuts in G is fixed parameter tractable in g. Specially, we give a 2O(g)n2 time algorithm for this problem. Our algorithm requires counting sets of cycles in a particular integer homology class. That we can count these cycles is an interesting result in itself as there are few prior results that are fixed parameter tractable and deal directly with integer homology. We also describe an algorithm which, after running our algorithm to count minimum cuts once, can sample an (s, t)-minimum cut uniformly at random in O(n log n) time per sample