Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms

Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

33 Citations (Scopus)

Abstract

Consider the following “local” cut-detection problem in a directed graph: We are given a seed vertex x and need to remove at most k edges so that at most ν edges can be reached from x (a “local” cut) or output to indicate that no such cut exists. If we are given query access to the input graph, then this problem can in principle be solved without reading the whole graph and with query complexity depending on k and ν. In this paper we consider a slack variant of this problem where, when such a cut exists, we can output a cut with up to O(kν) edges reachable from x. We present a simple randomized algorithm spending O(k2ν) time and O(kν) queries for the above variant, improving in particular a previous time bound of O(kO(k)ν) by Chechik et al. [SODA'17]. We also extend our algorithm to handle an approximate variant. We demonstrate that these local algorithms are versatile primitives for designing substantially improved algorithms for classic graph problems by providing the following three applications. (Throughout, Õ(T) hides polylog(T).) 1. A randomized algorithm for the classic k-vertex connectivity problem that takes near-linear time when k = O(polylog(n)), namely Õ(m + nk3) time in undirected graphs. Prior to our work, the state of the art for this range of k were linear-time algorithms for k ≤ 3 [Tarjan FOCS'71; Hopcroft, Tarjan SICOMP'73] and a recent algorithm with Õ(m + n4/3k7/3) time [Nanongkai et al., STOC'19]. The story is the same for directed graphs where our Õ(mk2)-time algorithm is near-linear when k = O(polylog(n)). Our techniques also yield an improved approximation scheme. 2. Property testing algorithms for k-edge and -vertex connectivity with query complexities that are near-linear in k, exponentially improving the state-of-the-art. This resolves two open problems, one by Goldreich and Ron [STOC'97] and one by Orenstein and Ron [Theor. Comput. Sci.'11]. 3. A faster algorithm for computing the maximal kedge connected subgraphs, improving prior work of Chechik et al. [SODA'17].

Original languageEnglish
Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
EditorsShuchi Chawla
PublisherACM
Pages2046-2065
Number of pages20
ISBN (Electronic)9781611975994
DOIs
Publication statusPublished - 1 Jan 2020
MoE publication typeA4 Conference publication
EventACM-SIAM Symposium on Discrete Algorithms - Salt Lake City, United States
Duration: 5 Jan 20208 Jan 2020
Conference number: 31

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
Country/TerritoryUnited States
CitySalt Lake City
Period05/01/202008/01/2020

Fingerprint

Dive into the research topics of 'Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms'. Together they form a unique fingerprint.

Cite this