Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimum Cuts in Directed Graphs via $sqrt{n}$ Max-Flows
220
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 algorithm to find a mincut in an $n$-vertex, $m$-edge weighted directed graph using $tilde O(sqrt{n})$ calls to any maxflow subroutine. Using state of the art maxflow algorithms, this yields a directed mincut algorithm that runs in $tilde O(msqrt{n} + n^2)$ time. This improves on the 30 year old bound of $tilde O(mn)$ obtained by Hao and Orlin for this problem.
rate research
Read More
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.
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.
Let $mathcal{D}$ be a set of $n$ disks in the plane. The disk graph $G_mathcal{D}$ for $mathcal{D}$ is the undirected graph with vertex set $mathcal{D}$ in which two disks are joined by an edge if and only if they intersect. The directed transmission graph $G^{rightarrow}_mathcal{D}$ for $mathcal{D}$ is the directed graph with vertex set $mathcal{D}$ in which there is an edge from a disk $D_1 in mathcal{D}$ to a disk $D_2 in mathcal{D}$ if and only if $D_1$ contains the center of $D_2$. Given $mathcal{D}$ and two non-intersecting disks $s, t in mathcal{D}$, we show that a minimum $s$-$t$ vertex cut in $G_mathcal{D}$ or in $G^{rightarrow}_mathcal{D}$ can be found in $O(n^{3/2}text{polylog} n)$ expected time. To obtain our result, we combine an algorithm for the maximum flow problem in general graphs with dynamic geometric data structures to manipulate the disks. As an application, we consider the barrier resilience problem in a rectangular domain. In this problem, we have a vertical strip $S$ bounded by two vertical lines, $L_ell$ and $L_r$, and a collection $mathcal{D}$ of disks. Let $a$ be a point in $S$ above all disks of $mathcal{D}$, and let $b$ a point in $S$ below all disks of $mathcal{D}$. The task is to find a curve from $a$ to $b$ that lies in $S$ and that intersects as few disks of $mathcal{D}$ as possible. Using our improved algorithm for minimum cuts in disk graphs, we can solve the barrier resilience problem in $O(n^{3/2}text{polylog} n)$ expected time.
In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the balance of the input graph, which smoothly interpolates between undirected and directed graphs. We give nearly matching upper and lower bounds for both for-all (cf. Benczur and Karger, STOC 1996) and for-each (Andoni et al., ITCS 2016) cut sparsifiers/sketches as a function of cut balance, defined the maximum ratio of the cut value in the two directions of a directed graph (Ene et al., STOC 2016). We also show an interesting application of digraph sparsification via cut balance by using it to give a very short proof of a celebrated maximum flow result of Karger and Levine (STOC 2002).
Given a capacitated undirected graph $G=(V,E)$ with a set of terminals $K subset V$, a mimicking network is a smaller graph $H=(V_H,E_H)$ that exactly preserves all the minimum cuts between the terminals. Specifically, the vertex set of the sparsifier $V_H$ contains the set of terminals $K$ and for every bipartition $U, K-U $ of the terminals $K$, the size of the minimum cut separating $U$ from $K-U$ in $G$ is exactly equal to the size of the minimum cut separating $U$ from $K-U$ in $H$. This notion of a mimicking network was introduced by Hagerup, Katajainen, Nishimura and Ragde (1995) who also exhibited a mimicking network of size $2^{2^{k}}$ for every graph with $k$ terminals. The best known lower bound on the size of a mimicking network is linear in the number of terminals. More precisely, the best known lower bound is $k+1$ for graphs with $k$ terminals (Chaudhuri et al. 2000). In this work, we improve both the upper and lower bounds reducing the doubly-exponential gap between them to a single-exponential gap. Specifically, we obtain the following upper and lower bounds on mimicking networks: 1) Given a graph $G$, we exhibit a construction of mimicking network with at most $(|K|-1)$th Dedekind number ($approx 2^{{(k-1)} choose {lfloor {{(k-1)}/2} rfloor}}$) of vertices (independent of size of $V$). Furthermore, we show that the construction is optimal among all {it restricted mimicking networks} -- a natural class of mimicking networks that are obtained by clustering vertices together. 2) There exists graphs with $k$ terminals that have no mimicking network of size smaller than $2^{frac{k-1}{2}}$. We also exhibit improved constructions of mimicking networks for trees and graphs of bounded tree-width.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
