Counting and Sampling Minimum Cuts in Genus g Graphs |
| |
Authors: | Erin W. Chambers Kyle Fox Amir Nayyeri |
| |
Affiliation: | 1. Department of Mathematics and Computer Science, Saint Louis University, Saint Louis, MO, USA 2. Department of Computer Science, Duke University, Durham, NC, USA 3. School of Electrical Engineering and Computer Science, Oregon State University, Corvallis, OR, USA
|
| |
Abstract: | 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 computing the number of minimum ((s,t)) -cuts in (G) is fixed-parameter tractable in (g) . Specifically, we give a (2^{O(g)} n^2) 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 no 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|