Optimal vertex connectivity oracles

DOI10.1145/3519935.3519945MaRDI QIDQ6083472zbMATH OpenOpenAlexFDO

Authors Seth Pettie, Thatchaphol Saranurak

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.00408

zbMATH Keywords

data structuresgraph connectivityspace lower bounds

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: A $k$-vertex connectivity oracle for undirected $G$ is a data structure that, given $u,vinV(G)$, reports $mink,kappa(u,v)$, where $kappa(u,v)$ is the pairwise vertex connectivity between $u,v$. There are three main measures of efficiency: construction time, query time, and space. Prior work of Izsak and Nutov shows that a data structure of total size $ildeO(kn)$ can even be encoded as a $ildeO(k)$-bit labeling scheme so that vertex-connectivity queries can be answered in $ildeO(k)$ time. The construction time is polynomial, but unspecified. In this paper we address the top three complexity measures: Space, Query Time, and Construction Time. We give an $Omega(kn)$-bit lower bound on any vertex connectivity oracle. We construct an optimal-space connectivity oracle in max-flow time that answers queries in $O(logn)$ time, independent of $k$.

Cited in

(6)

• Connectivity Oracles for Planar Graphs
• A nearly optimal oracle for avoiding failed vertices and edges
• Maximum flow and minimum-cost flow in almost-linear time
• Data structures for node connectivity queries
• Near-optimal vertex fault-tolerant labels for Steiner connectivity
• An optimal 3-fault-tolerant connectivity oracle

This page was built for publication: Optimal vertex connectivity oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083472)