Optimal vertex connectivity oracles

A k-vertex connectivity oracle for an undirected graph G is a data structure that, given u, v ∈ V (G), reports minκ(u, v), k+1, where κ(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 [IN12] produced a data structure of O(kn log n) words, which can even be encoded as a O(k log 3 n)-bit labeling scheme, that can answer vertex-connectivity queries in O(k log n) time. The construction time is polynomial, but unspecified. In this paper we address the top three complexity measures.