Minimum Cuts in Surface Graphs
Minimum Cuts in Surface Graphs
复制标题
DOI：
10.1137/19m1291820
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
E. Chambers;Jeff Erickson;K. Fox;A. Nayyeri
中科院分区：
文献类型：
--
作者：
E. Chambers;Jeff Erickson;K. Fox;A. Nayyeri
我们描述了有效计算最小$（S，T）$的算法 - 切割和全球最小剪切图表的表面插入图。给定带有$ n $顶点的边缘加权的无向图$ g $嵌入在属$ g $的可定向表面上，我们的算法可以解决$ g^{o（g）} n \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log n $或$ 2^{o（g）} n \ log n $ time，以更好的情况。当$ g $是一个常数时，我们的$ g^{o（g）} n \ log \ log n $ time算法符合以计算平面图中最低切割的最佳运行时间。我们的最低削减算法依赖于在给定的$ \ Mathbb {z} _2 $ - 本体学类中找到最小重量子图的问题，我们也为此问题提供了有效的算法。如果将$ g $嵌入具有$ b $边界组件的表面中，则这些算法以$（g + b）^{o（g + b）} n \ log \ log \ log \ log \ n $和$ 2^{o（g + b）} n \ log n \ log n $ time运行。我们还证明，找到一个与单个输入周期同源的最小重量子图是NP-HARD，这表明对于后一种问题，可能无法改善对$ G $的指数依赖性。
We describe algorithms to efficiently compute minimum $(s,t)$-cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph $G$ with $n$ vertices embedded on an orientable surface of genus $g$, our algorithms can solve either problem in $g^{O(g)} n \log \log n$ or $2^{O(g)} n \log n$ time, whichever is better. When $g$ is a constant, our $g^{O(g)} n \log \log n$ time algorithms match the best running times known for computing minimum cuts in planar graphs. Our algorithms for minimum cuts rely on reductions to the problem of finding a minimum-weight subgraph in a given $\mathbb{Z}_2$-homology class, and we give efficient algorithms for this latter problem as well. If $G$ is embedded on a surface with $b$ boundary components, these algorithms run in $(g + b)^{O(g + b)} n \log \log n$ and $2^{O(g + b)} n \log n$ time. We also prove that finding a minimum-weight subgraph homologous to a single input cycle is NP-hard, showing it is likely impossible to improve upon the exponential dependencies on $g$ for this latter problem.