期刊
STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING
卷 -, 期 -, 页码 384-395出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3406325.3451114
关键词
minimum cut; deterministic algorithms; de-randomization; graph sparsification
This study presents a deterministic mincut algorithm for weighted, undirected graphs, answering a question from Karger. By partially derandomizing the Benczur-Karger graph sparsification technique and designing an efficient pessimistic estimator to capture graph cuts, as well as utilizing the expander decomposition framework, the researchers achieved the desired result. As a side-effect, a structural representation of all approximate mincuts in a graph was obtained, potentially useful for future applications.
We present a deterministic (global) mincut algorithm for weighted, undirected graphs that runs in m(1)(+o(1)) time, answering an open question of Karger from the 1990s. To obtain our result, we derandomize the construction of the skeleton graph in Karger's near-linear time mincut algorithm, which is its only randomized component. In particular, we partially de-randomize the well-known Benczur-Karger graph sparsification technique by random sampling, which we accomplish by the method of pessimistic estimators. Our main technical component is designing an efficient pessimistic estimator to capture the cuts of a graph, which involves harnessing the expander decomposition framework introduced in recent work by Goranci et al. (SODA 2021). As a side-effect, we obtain a structural representation of all approximate mincuts in a graph, which may have future applications.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据