Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
89
0
0.0
(
0
)
Added by
Thatchaphol Saranurak
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give an $n^{2+o(1)}$-time algorithm for finding $s$-$t$ min-cuts for all pairs of vertices $s$ and $t$ in a simple, undirected graph on $n$ vertices. We do so by constructing a Gomory-Hu tree (or cut equivalent tree) in the same running time, thereby improving on the recent bound of $tilde{O}(n^{2.5})$ by Abboud et al. (FOCS 2021). Our running time is nearly optimal as a function of $n$.
rate research
Read More
Minimum-weight cut (min-cut) is a basic measure of a networks connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.g. [Ghaffari, Kuhn, DISC13; Nanongkai, Su, DISC14]) can guarantee a solution that is $(1+epsilon)$-approximation at best while the exact $tilde O(n^{0.8}D^{0.2} + n^{0.9})$-time algorithm [Ghaffari, Nowicki, Thorup, SODA20] works only on *simple* networks (no weights and no parallel edges). Here $n$ and $D$ denote the networks number of vertices and hop-diameter, respectively. For the weighted case, the best bound was $tilde O(n)$ [Daga, Henzinger, Nanongkai, Saranurak, STOC19]. In this paper, we provide an *exact* $tilde O(sqrt n + D)$-time algorithm for computing min-cut on *weighted* networks. Our result improves even the previous algorithm that works only on simple networks. Its time complexity matches the known lower bound up to polylogarithmic factors. At the heart of our algorithm are a clever routing trick and two structural lemmas regarding the structure of a minimum cut of a graph. These two structural lemmas considerably strengthen and generalize the framework of Mukhopadhyay-Nanongkai [STOC20] and can be of independent interest.
We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $mgeq n^{1+epsilon}$ for any constant $epsilon>0$, our algorithm requires $O(m log n)$ work and $O(log^3 n)$ depth and succeeds with high probability. Its work matches the best $O(m log n)$ runtime for sequential algorithms [MN STOC 2020, GMW SOSA 2021]. This improves the previous best work by Geissmann and Gianinazzi [SPAA 2018] by $O(log^3 n)$ factor, while matching the depth of their algorithm. To do this, we design a work-efficient approximation algorithm and parallelize the recent sequential algorithms [MN STOC 2020; GMW SOSA 2021] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching.
We consider high dimensional variants of the maximum flow and minimum cut problems in the setting of simplicial complexes and provide both algorithmic and hardness results. By viewing flows and cuts topologically in terms of the simplicial (co)boundary operator we can state these problems as linear programs and show that they are dual to one another. Unlike graphs, complexes with integral capacity constraints may have fractional max-flows. We show that computing a maximum integral flow is NP-hard. Moreover, we give a combinatorial definition of a simplicial cut that seems more natural in the context of optimization problems and show that computing such a cut is NP-hard. However, we provide conditions on the simplicial complex for when the cut found by the linear program is a combinatorial cut. For $d$-dimensional simplicial complexes embedded into $mathbb{R}^{d+1}$ we provide algorithms operating on the dual graph: computing a maximum flow is dual to computing a shortest path and computing a minimum cut is dual to computing a minimum cost circulation. Finally, we investigate the Ford-Fulkerson algorithm on simplicial complexes, prove its correctness, and provide a heuristic which guarantees it to halt.
Let $G = (V,E,w)$ be a weighted undirected graph on $|V| = n$ vertices and $|E| = m$ edges, let $k ge 1$ be any integer, and let $epsilon < 1$ be any parameter. We present the following results on fast constructions of spanners with near-optimal sparsity and lightness, which culminate a long line of work in this area. (By near-optimal we mean optimal under ErdH{o}s girth conjecture and disregarding the $epsilon$-dependencies.) - There are (deterministic) algorithms for constructing $(2k-1)(1+epsilon)$-spanners for $G$ with a near-optimal sparsity of $O(n^{1/k} log(1/epsilon)/epsilon))$. The first algorithm can be implemented in the pointer-machine model within time $O(malpha(m,n) log(1/epsilon)/epsilon) + SORT(m))$, where $alpha( , )$ is the two-parameter inverse-Ackermann function and $SORT(m)$ is the time needed to sort $m$ integers. The second algorithm can be implemented in the WORD RAM model within time $O(m log(1/epsilon)/epsilon))$. - There is a (deterministic) algorithm for constructing a $(2k-1)(1+epsilon)$-spanner for $G$ that achieves a near-optimal bound of $O(n^{1/k}mathrm{poly}(1/epsilon))$ on both sparsity and lightness. This algorithm can be implemented in the pointer-machine model within time $O(malpha(m,n) mathrm{poly}(1/epsilon) + SORT(m))$ and in the WORD RAM model within time $O(m alpha(m,n) mathrm{poly}(1/epsilon))$. The previous fastest constructions of $(2k-1)(1+epsilon)$-spanners with near-optimal sparsity incur a runtime of is $O(min{m(n^{1+1/k}) + nlog n,k n^{2+1/k}})$, even regardless of the lightness. Importantly, the greedy spanner for stretch $2k-1$ has sparsity $O(n^{1/k})$ -- with no $epsilon$-dependence whatsoever, but its runtime is $O(m(n^{1+1/k} + nlog n))$. Moreover, the state-of-the-art lightness bound of any $(2k-1)$-spanner is poor, even regardless of the sparsity and runtime.
The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the total weight of edges between the two sets is maximized/minimized. Although these two problems are known to be NP-hard, there is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen et al. (SIAM J. Comput. 2005) gave an $O(2^tn^3)$-time algorithm when given a tree decomposition of width $t$ of the input graph, where $n$ is the number of vertices of the input graph. Eiben et al. (ESA 2019) improved the dependency of $n$ in the running time by giving an $O(8^tt^5n^2log n)$-time algorithm. Moreover, they showed that there is no $O(n^{2-varepsilon})$-time algorithm for trees under some reasonable complexity assumption. In this paper, we show an $O(2^t(tn)^2)$-time algorithm for both problems, which is asymptotically tight to their conditional lower bound. We also show that the exponential dependency of the treewidth is asymptotically optimal under the Strong Exponential Time Hypothesis. Finally, we discuss the (in)tractability of both problems with respect to special graph classes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
