Space Complexity of Vertex Connectivity Oracles
SIAM Journal on Computing · 30.04.2026 · 55 (2) · 280-306
DOI: 10.1137/23m1564845 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 02.03.2026. Verfasst von Seth Pettie und 2 weiteren Autor:innen. Die Arbeit nennt 66 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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.
Förderung
- National Science Foundation
Zitieren
APA
Pettie, S., Saranurak, T., & Yin, L. (2026). Space Complexity of Vertex Connectivity Oracles. SIAM Journal on Computing, 55(2), 280-306. https://doi.org/10.1137/23m1564845
Vancouver
Pettie S, Saranurak T, Yin L. Space Complexity of Vertex Connectivity Oracles. SIAM Journal on Computing. 2026;55(2):280-306. doi:10.1137/23m1564845
BibTeX
@article{Pettie2026,
author = {Pettie, Seth and Saranurak, Thatchaphol and Yin, Longhui},
title = {Space Complexity of Vertex Connectivity Oracles},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {2},
pages = {280--306},
doi = {10.1137/23m1564845}
}
EUVIMED