New Oracles and Labeling Schemes for Vertex Cut Queries

We study the succinct representations of vertex cuts by centralized oracles and labeling schemes. For an undirected \(n\)-vertex graph \(G = (V,E)\) and integer parameter \(f \ge 1\), the goal is supporting vertex cut queries: Given \(F \subseteq V\) with \(|F| \le f\), determine if \(F\) is a vertex cut in \(G\). In the centralized data structure setting, it is required to preprocess \(G\) into an \(f\)-vertex cut oracle that can answer such queries quickly, while occupying only small space. In the labeling setting, one should assign a short label to each vertex in \(G\), so that a cut query \(F\) can be answered by merely inspecting the labels assigned to the vertices in \(F\).