ﻻ يوجد ملخص باللغة العربية
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
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 termin
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 dis
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)bounda
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
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 kn