Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSparsification of Directed Graphs via Cut Balance
281
0
0.0
(
0
)
Added by
Yu Cheng
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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).
rate research
Read More
The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczur and Karger (1996) showed that given any $n$-vertex undirected weighted graph $G$ and a parameter $varepsilon in (0,1)$, there is a near-linear time algorithm that outputs a weighted subgraph $G$ of $G$ of size $tilde{O}(n/varepsilon^2)$ such that the weight of every cut in $G$ is preserved to within a $(1 pm varepsilon)$-factor in $G$. The graph $G$ is referred to as a {em $(1 pm varepsilon)$-approximate cut sparsifier} of $G$. Subsequent recent work has obtained a similar result for the more general problem of hypergraph cut sparsifiers. However, all known sparsification algorithms require $Omega(n + m)$ time where $n$ denotes the number of vertices and $m$ denotes the number of hyperedges in the hypergraph. Since $m$ can be exponentially large in $n$, a natural question is if it is possible to create a hypergraph cut sparsifier in time polynomial in $n$, {em independent of the number of edges}. We resolve this question in the affirmative, giving the first sublinear time algorithm for this problem, given appropriate query access to the hypergraph.
Let $G$ be a graph and $S, T subseteq V(G)$ be (possibly overlapping) sets of terminals, $|S|=|T|=k$. We are interested in computing a vertex sparsifier for terminal cuts in $G$, i.e., a graph $H$ on a smallest possible number of vertices, where $S cup T subseteq V(H)$ and such that for every $A subseteq S$ and $B subseteq T$ the size of a minimum $(A,B)$-vertex cut is the same in $G$ as in $H$. We assume that our graphs are unweighted and that terminals may be part of the min-cut. In previous work, Kratsch and Wahlstrom (FOCS 2012/JACM 2020) used connections to matroid theory to show that a vertex sparsifier $H$ with $O(k^3)$ vertices can be computed in randomized polynomial time, even for arbitrary digraphs $G$. However, since then, no improvements on the size $O(k^3)$ have been shown. In this paper, we draw inspiration from the renowned Bollobass Two-Families Theorem in extremal combinatorics and introduce the use of total orderings into Kratsch and Wahlstroms methods. This new perspective allows us to construct a sparsifier $H$ of $Theta(k^2)$ vertices for the case that $G$ is a DAG. We also show how to compute $H$ in time near-linear in the size of $G$, improving on the previous $O(n^{omega+1})$. Furthermore, $H$ recovers the closest min-cut in $G$ for every partition $(A,B)$, which was not previously known. Finally, we show that a sparsifier of size $Omega(k^2)$ is required, both for DAGs and for undirected edge cuts.
We give almost-linear-time algorithms for constructing sparsifiers with $n poly(log n)$ edges that approximately preserve weighted $(ell^{2}_2 + ell^{p}_p)$ flow or voltage objectives on graphs. For flow objectives, this is the first sparsifier construction for such mixed objectives beyond unit $ell_p$ weights, and is based on expander decompositions. For voltage objectives, we give the first sparsifier construction for these objectives, which we build using graph spanners and leverage score sampling. Together with the iterative refinement framework of [Adil et al, SODA 2019], and a new multiplicative-weights based constant-approximation algorithm for mixed-objective flows or voltages, we show how to find $(1+2^{-text{poly}(log n)})$ approximations for weighted $ell_p$-norm minimizing flows or voltages in $p(m^{1+o(1)} + n^{4/3 + o(1)})$ time for $p=omega(1),$ which is almost-linear for graphs that are slightly dense ($m ge n^{4/3 + o(1)}$).
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.
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $kleq log n$, and an error parameter $epsilon > 0$, our algorithm runs in space $tilde{O}(klog (Ncdot w_{mathrm{max}}/w_{mathrm{min}}))$ where $w_{mathrm{max}}$ and $w_{mathrm{min}}$ are the maximum and minimum edge weights in $G$, and produces a weighted graph $H$ with $tilde{O}(n^{1+2/k}/epsilon^2)$ edges that spectrally approximates $G$, in the sense of Spielmen and Teng [ST04], up to an error of $epsilon$. Our algorithm is based on a new bounded-independence analysis of Spielman and Srivastavas effective resistance based edge sampling algorithm [SS08] and uses results from recent work on space-bounded Laplacian solvers [MRSV17]. In particular, we demonstrate an inherent tradeoff (via upper and lower bounds) between the amount of (bounded) independence used in the edge sampling algorithm, denoted by $k$ above, and the resulting sparsity that can be achieved.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
