Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVertex Connectivity in Poly-logarithmic Max-flows
224
0
0.0
(
0
)
Added by
Sorrachai Yingchareonthawornchai
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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
rate research
Read More
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.
Updating and querying on a range is a classical algorithmic problem with a multitude of applications. The Segment Tree data structure is particularly notable in handling the range query and update operations. A Segment Tree divides the range into disjoint segments and merges them together to perform range queries and range updates elegantly. Although this data structure is remarkably potent for 1-dimensional problems, it falls short in higher dimensions. Lazy Propagation enables the operations to be computed in $O(logn)$ time in a single dimension. However, the concept of lazy propagation could not be translated to higher-dimensional cases, which imposes a time complexity of $O(n^{k-1} ; logn)$ for operations on $k$-dimensional data. In this work, we have made an attempt to emulate the idea of lazy propagation differently so that it can be applied for 2-dimensional cases. Moreover, the proposed modification should be capable of performing most general aggregate functions similar to the original Segment Tree, and can also be extended to even higher dimensions. Our proposed algorithm manages to perform range sum queries and updates in $O(log^2 n)$ time for a 2-dimensional problem, which becomes $O(log^d n)$ for a $d$-dimensional situation.
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 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 provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution scheme (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For the vertex arrival, our result is tight. Interestingly, a pricing-based prophet inequality with comparable competitive ratios is unknown.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
