Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPractical Fully Dynamic Minimum Cut Algorithms
101
0
0.0
(
0
)
Added by
Alexander Noe
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present a practically efficient algorithm for maintaining a global minimum cut in large dynamic graphs under both edge insertions and deletions. While there has been theoretical work on this problem, our algorithm is the first implementation of a fully-dynamic algorithm. The algorithm uses the theoretical foundation and combines it with efficient and finely-tuned implementations to give an algorithm that can maintain the global minimum cut of a graph with rapid update times. We show that our algorithm gives up to multiple orders of magnitude speedup compared to static approaches both on edge insertions and deletions.
rate research
Read More
In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms.
Maintaining maximal independent set in dynamic graph is a fundamental open problem in graph theory and the first sublinear time deterministic algorithm was came up by Assadi, Onak, Schieber and Solomon(STOC18), which achieves $O(m^{3/4})$ amortized update time. We have two main contributions in this paper. We present a new simple deterministic algorithm with $O(m^{2/3}sqrt{log m})$ amortized update time, which improves the previous best result. And we also present the first randomized algorithm with expected $O(sqrt{m}log^{1.5}m)$ amortized time against an oblivious adversary.
In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like {sc Degree}, {sc Neighbor}, and {sc Adjacency} queries. Given $epsilon in (0,1)$, the algorithm with high probability outputs an estimate $hat{t}$ satisfying the following $(1-epsilon) t leq hat{t} leq (1+epsilon) t$, where $m$ is the number of edges in the graph and $t$ is the size of minimum cut in the graph. The expected number of local queries used by our algorithm is $minleft{m+n,frac{m}{t}right}mbox{poly}left(log n,frac{1}{epsilon}right)$ where $n$ is the number of vertices in the graph. Eden and Rosenbaum showed that $Omega(m/t)$ many local queries are required for approximating the size of minimum cut in graphs. These two results together resolve the query complexity of the problem of estimating the size of minimum cut in graphs using local queries. Building on the lower bound of Eden and Rosenbaum, we show that, for all $t in mathbb{N}$, $Omega(m)$ local queries are required to decide if the size of the minimum cut in the graph is $t$ or $t-2$. Also, we show that, for any $t in mathbb{N}$, $Omega(m)$ local queries are required to find all the minimum cut edges even if it is promised that the input graph has a minimum cut of size $t$. Both of our lower bound results are randomized, and hold even if we can make {sc Random Edge} query apart from local queries.
Consider the following 2-respecting min-cut problem. Given a weighted graph $G$ and its spanning tree $T$, find the minimum cut among the cuts that contain at most two edges in $T$. This problem is an important subroutine in Kargers celebrated randomized near-linear-time min-cut algorithm [STOC96]. We present a new approach for this problem which can be easily implemented in many settings, leading to the following randomized min-cut algorithms for weighted graphs. * An $O(mfrac{log^2 n}{loglog n} + nlog^6 n)$-time sequential algorithm: This improves Kargers $O(m log^3 n)$ and $O(mfrac{(log^2 n)log (n^2/m)}{loglog n} + nlog^6 n)$ bounds when the input graph is not extremely sparse or dense. Improvements over Kargers bounds were previously known only under a rather strong assumption that the input graph is simple [Henzinger et al. SODA17; Ghaffari et al. SODA20]. For unweighted graphs with parallel edges, our bound can be improved to $O(mfrac{log^{1.5} n}{loglog n} + nlog^6 n)$. * An algorithm requiring $tilde O(n)$ cut queries to compute the min-cut of a weighted graph: This answers an open problem by Rubinstein et al. ITCS18, who obtained a similar bound for simple graphs. * A streaming algorithm that requires $tilde O(n)$ space and $O(log n)$ passes to compute the min-cut: The only previous non-trivial exact min-cut algorithm in this setting is the 2-pass $tilde O(n)$-space algorithm on simple graphs [Rubinstein et al., ITCS18] (observed by Assadi et al. STOC19). In contrast to Kargers 2-respecting min-cut algorithm which deploys sophisticated dynamic programming techniques, our approach exploits some cute structural properties so that it only needs to compute the values of $tilde O(n)$ cuts corresponding to removing $tilde O(n)$ pairs of tree edges, an operation that can be done quickly in many settings.
Given a graph $G=(V,E)$ with two distinguished vertices $s,tin V$ and an integer parameter $L>0$, an {em $L$-bounded cut} is a subset $F$ of edges (vertices) such that the every path between $s$ and $t$ in $Gsetminus F$ has length more than $L$. The task is to find an $L$-bounded cut of minimum cardinality. Though the problem is very simple to state and has been studied since the beginning of the 70s, it is not much understood yet. The problem is known to be $cal{NP}$-hard to approximate within a small constant factor even for $Lgeq 4$ (for $Lgeq 5$ for the vertex cuts). On the other hand, the best known approximation algorithm for general graphs has approximation ratio only $mathcal{O}({n^{2/3}})$ in the edge case, and $mathcal{O}({sqrt{n}})$ in the vertex case, where $n$ denotes the number of vertices. We show that for planar graphs, it is possible to solve both the edge- and the vertex-version of the problem optimally in time $mathcal{O}(L^{3L}n)$. That is, the problem is fixed parameter tractable (FPT) with respect to $L$ on planar graphs. Furthermore, we show that the problem remains FPT even for bounded genus graphs, a super class of planar graphs. Our second contribution deals with approximations of the vertex version of the problem. We describe an algorithm that for a given a graph $G$, its tree decomposition of treewidth $tau$ and vertices $s$ and $t$ computes a $tau$-approximation of the minimum $L$-bounded $s-t$ vertex cut; if the decomposition is not given, then the approximation ratio is $mathcal{O}(tau sqrt{log tau})$. For graphs with treewidth bounded by $mathcal{O}(n^{1/2-epsilon})$ for any $epsilon>0$, but not by a constant, this is the best approximation in terms of~$n$ that we are aware of.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
