This content will become publicly available on April 30, 2027

Title: Space Complexity of Vertex Connectivity Oracles
Abstract. A [Formula: see text]- vertex connectivity oracle for an undirected graph [Formula: see text] is a data structure that, given [Formula: see text], reports [Formula: see text], where [Formula: see text] is the pairwise vertex connectivity between [Formula: see text]. There are three main measures of efficiency: construction time, query time, and space. Prior work of Izsak and Nutov [ Inform. Process. Lett., 112 (2012), pp. 39–43] produced a data structure of [Formula: see text] words, which can even be encoded as a [Formula: see text]-bit labeling scheme, that can answer vertex connectivity queries in [Formula: see text] time. The construction time is polynomial but unspecified. In this paper, we address the top three complexity measures. (1) Space: We prove that any [Formula: see text]-vertex connectivity oracle requires [Formula: see text] bits of space for any [Formula: see text]. This proves that the Iszak–Nutov data structure is optimal up to polylogarithmic factors for every [Formula: see text] and that the sparsifiers of Nagamochi and Ibaraki [ Algorithmica, 7 (1992), pp. 583–596] are optimal compression schemes for [Formula: see text]-vertex connectivity up to a logarithmic factor. In particular, whereas all edge connectivities can be efficiently compressed (as a weighted [Formula: see text]-edge Gomory–Hu tree), vertex connectivity admits no asymptotic compression: [Formula: see text] bits are necessary. We design a variation on Izsak and Nutov’s data structure that uses [Formula: see text] words of space. (2) Query time: We answer queries in [Formula: see text] time, improving on the [Formula: see text] time bound of Izsak and Nutov [ Inform. Process. Lett., 112 (2012), pp. 39–43]. The main idea is to build instances of [Formula: see text] data structures, with additional structure based on affine planes. This structure allows for query time that is linear in the output size, which evades some conditional lower bounds that are polynomial in the query set sizes [ 42 ,  51 ]. (3) Construction time: Our data structure can be constructed in the time of [Formula: see text] max-flow computations, namely, [Formula: see text] time, using the recent near-linear time flow algorithm of [ 13 ]. The main technical contribution here is a fast algorithm to compute a [Formula: see text]-approximate Gomory–Hu tree for element connectivity in the time of [Formula: see text] max-flow computations. Element connectivity is a notion that generalizes edge and vertex connectivity.  more » « less
Award ID(s):
2238138
PAR ID:
10711754
Author(s) / Creator(s):
; ;
Publisher / Repository:
Society for Industrial and Applied Mathematics
Date Published:
Journal Name:
SIAM Journal on Computing
Volume:
55
Issue:
2
ISSN:
0097-5397
Page Range / eLocation ID:
280 to 306
Subject(s) / Keyword(s):
Sponsoring Org:
National Science Foundation
More Like this
  1. Bhattacharya, Sayan; Nanongkai, Danupon; Benedikt, Michael; Puppis, Gabriele (Ed.)
    Abstract: We study connectivity oracle under vertex failures, one of the most fundamental graph data structures with many applications. We provide a new deterministic connectivity oracle that handles update in O(k⁶) time and answers query in O(k) time, while using 2^O(k²) n + O(k²n α_c(n)) space and k^O(k²) n + O(m + k³ n log² n + k⁶n log n) preprocessing time. Although some previous works achieve k² ⋅ n^o(1) update time and O(k) query time [Long and Saranurak, 2022; Yaowei Long and Yunfan Wang, 2024], the update time is still n-dependent, while oracles that have n-independent update and query times [Michal Pilipczuk et al., 2022; Jan van den Brand and Thatchaphol Saranurak, 2019] cannot achieve optimal O(k) query time [Monika Henzinger et al., 2015] and often have Ω(n²) space and processing time. Our solution would be the first vertex-failure connectivity oracle that achieves O(k) query time with update time completely independent of n, while improving space usage and having competitive preprocessing time. 
    more » « less
  2. Starting with a vertex-weighted pointed graph [Formula: see text], we form the free loop algebra [Formula: see text] defined in Hartglass–Penneys’ article on canonical [Formula: see text]-algebras associated to a planar algebra. Under mild conditions, [Formula: see text] is a non-nuclear simple [Formula: see text]-algebra with unique tracial state. There is a canonical polynomial subalgebra [Formula: see text] together with a Dirac number operator [Formula: see text] such that [Formula: see text] is a spectral triple. We prove the Haagerup-type bound of Ozawa–Rieffel to verify [Formula: see text] yields a compact quantum metric space in the sense of Rieffel. We give a weighted analog of Benjamini–Schramm convergence for vertex-weighted pointed graphs. As our [Formula: see text]-algebras are non-nuclear, we adjust the Lip-norm coming from [Formula: see text] to utilize the finite dimensional filtration of [Formula: see text]. We then prove that convergence of vertex-weighted pointed graphs leads to quantum Gromov–Hausdorff convergence of the associated adjusted compact quantum metric spaces. As an application, we apply our construction to the Guionnet–Jones–Shyakhtenko (GJS) [Formula: see text]-algebra associated to a planar algebra. We conclude that the compact quantum metric spaces coming from the GJS [Formula: see text]-algebras of many infinite families of planar algebras converge in quantum Gromov–Hausdorff distance. 
    more » « less
  3. null (Ed.)
    We propose an Euler transformation that transforms a given [Formula: see text]-dimensional cell complex [Formula: see text] for [Formula: see text] into a new [Formula: see text]-complex [Formula: see text] in which every vertex is part of the same even number of edges. Hence every vertex in the graph [Formula: see text] that is the [Formula: see text]-skeleton of [Formula: see text] has an even degree, which makes [Formula: see text] Eulerian, i.e., it is guaranteed to contain an Eulerian tour. Meshes whose edges admit Eulerian tours are crucial in coverage problems arising in several applications including 3D printing and robotics. For [Formula: see text]-complexes in [Formula: see text] ([Formula: see text]) under mild assumptions (that no two adjacent edges of a [Formula: see text]-cell in [Formula: see text] are boundary edges), we show that the Euler transformed [Formula: see text]-complex [Formula: see text] has a geometric realization in [Formula: see text], and that each vertex in its [Formula: see text]-skeleton has degree [Formula: see text]. We bound the numbers of vertices, edges, and [Formula: see text]-cells in [Formula: see text] as small scalar multiples of the corresponding numbers in [Formula: see text]. We prove corresponding results for [Formula: see text]-complexes in [Formula: see text] under an additional assumption that the degree of a vertex in each [Formula: see text]-cell containing it is [Formula: see text]. In this setting, every vertex in [Formula: see text] is shown to have a degree of [Formula: see text]. We also present bounds on parameters measuring geometric quality (aspect ratios, minimum edge length, and maximum angle of cells) of [Formula: see text] in terms of the corresponding parameters of [Formula: see text] for [Formula: see text]. Finally, we illustrate a direct application of the proposed Euler transformation in additive manufacturing. 
    more » « less
  4. 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 1974, Aho Hopcroft and Ullman asked if vertex connectivity can be computed in linear time. Despite the substantial effort in the past five decades, the best-known running time is O-tilde(mn) by Henzinger-Rao-Gabow (FOCS 1996). Indeed, no algorithm with an o(mn) running time is known even if we assume a linear-time max-flow algorithm. In this article, we give an affirmative answer to this long-standing open problem (up to a sub-polynomial factor). We present a randomized reduction from the vertex connectivity problem to the max-flow problem which incurs only a poly-logarithmic overhead in runtime. Using this reduction, we can solve vertex connectivity in almost linear time by using the celebrated almost-linear-time max-flow algorithms by Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) and Brand-Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva-Sidford (FOCS 2023). Using our new techniques, we also obtain an algorithm for directed vertex connectivity with a running time of n^(2+o(1)) time which improves the best-known bound of O-tilde(mn) by Henzinger-Rao-Gabow (FOCS 1996). 
    more » « less
  5. We construct a right inverse of the trace operator [Formula: see text] on the reference triangle [Formula: see text] that maps suitable piecewise polynomial data on [Formula: see text] into polynomials of the same degree and is bounded in all [Formula: see text] norms with [Formula: see text] and [Formula: see text]. The analysis relies on new stability estimates for three classes of single edge operators. We then generalize the construction for [Formula: see text]th-order normal derivatives, [Formula: see text]. 
    more » « less