Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVertex Sparsification for Edge Connectivity
296
0
0.0
(
0
)
Added by
Yang P. Liu
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter $c$, find a smaller graph, which we call connectivity-$c$ mimicking network, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that connectivity-$c$ mimicking networks with $O(kc^4)$ edges exist and can be found in time $m(clog n)^{O(c)}$. We also give a separate algorithm that constructs such graphs with $k cdot O(c)^{2c}$ edges in time $mc^{O(c)}log^{O(1)}n$. These results lead to the first data structures for answering fully dynamic offline $c$-edge-connectivity queries for $c ge 4$ in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.
rate research
Read More
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA19] states that in every $n$-vertex graph $G$ with maximum degree $Delta$, sampling $O(log{n})$ colors per each vertex independently from $Delta+1$ colors almost certainly allows for proper coloring of $G$ from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for $(Delta+1)$ coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we further study palette sparsification problems: * We prove that for $(1+varepsilon) Delta$ coloring, sampling only $O_{varepsilon}(sqrt{log{n}})$ colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors. * A natural family of graphs with chromatic number much smaller than $(Delta+1)$ are triangle-free graphs which are $O(frac{Delta}{ln{Delta}})$ colorable. We prove that sampling $O(Delta^{gamma} + sqrt{log{n}})$ colors per vertex is sufficient and necessary to obtain a proper $O_{gamma}(frac{Delta}{ln{Delta}})$ coloring of triangle-free graphs. * We show that sampling $O_{varepsilon}(log{n})$ colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of $(1+varepsilon) cdot deg(v)$ arbitrary colors, or even only $deg(v)+1$ colors when the lists are the sets ${1,ldots,deg(v)+1}$. Similar to previous work, our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.
We show a deterministic algorithm for computing edge connectivity of a simple graph with $m$ edges in $m^{1+o(1)}$ time. Although the fastest deterministic algorithm by Henzinger, Rao, and Wang [SODA17] has a faster running time of $O(mlog^{2}mloglog m)$, we believe that our algorithm is conceptually simpler. The key tool for this simplication is the expander decomposition. We exploit it in a very straightforward way compared to how it has been previously used in the literature.
The vertex connectivity of an $m$-edge $n$-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in $tilde O(m^{alpha})$ time for any $alpha ge 1$, if there is a $m^{alpha}$-time maxflow algorithm. Using the current best maxflow algorithm that runs in $m^{4/3+o(1)}$ time (Kathuria, Liu and Sidford, FOCS 2020), this yields a $m^{4/3+o(1)}$-time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an $tilde O(mn)$-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an $o(mn)$ running time was known before our work, even if we assume an $tilde O(m)$-time maxflow algorithm. Our new technique is robust enough to also improve the best $tilde O(mn)$-time bound for directed vertex connectivity to $mn^{1-1/12+o(1)}$ time
The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph $G$ and a spanning tree $T$ for it, and the goal is to augment $T$ with a minimum set of edges $Aug$ from $G$, such that $T cup Aug$ is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and J{a}J{a}, SICOMP 1981. Recently, a 3/2-approximation was given for unweighted TAP by Kortsarz and Nutov, TALG 2016. Recent breakthroughs give an approximation of 1.458 for unweighted TAP [Grandoni et al., STOC 2018], and approximations better than 2 for bounded weights [Adjiashvili, SODA 2017; Fiorini et al., SODA 2018]. In this paper, we provide the first fast distributed approximations for TAP. We present a distributed $2$-approximation for weighted TAP which completes in $O(h)$ rounds, where $h$ is the height of $T$. When $h$ is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in $O(D+sqrt{n}log^*{n})$ rounds, where $n$ is the number of vertices and $D$ is the diameter of $G$. Immediate consequences of our results are an $O(D)$-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an $O(h_{MST}+sqrt{n}log^{*}{n})$-round 3-approximation algorithm for the weighted case, where $h_{MST}$ is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augmenting the connectivity of any connected spanning subgraph to 2. Finally, we complement our study with proving lower bounds for distributed approximations of TAP.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
