New Oracles and Labeling Schemes for Vertex Cut Queries

Yonggang Jiang, Merav Parter, Asaf Petruschka · 2025

Read New Oracles and Labeling Schemes for Vertex Cut Queries by Yonggang Jiang, Merav Parter, Asaf Petruschka (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13596.txt.

Description

Yonggang Jiang, Merav Parter, and Asaf Petruschka build compact tools for vertex cut queries in a 2025 paper. A vertex cut is a set whose removal splits a graph. Queries ask whether a small given set forms a cut. Short labels or a small oracle could answer without the full graph.

Related source-target cut problems already had efficient solutions. The global cut version stayed essentially open, especially for larger sets. The authors give the first major progress on both fronts. Every graph admits cut labels of near-matching length to a recent lower bound. A central oracle uses near-linear space and fast query time. Matching lower bounds show the oracles are near-optimal, under standard assumptions. For well-connected graphs, minimum cut queries run even faster. The work closes much of a long-standing gap. Succinct graph data structures gain a new core result.

Catalog record

CREATORYonggang Jiang, Merav Parter, Asaf Petruschka
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE129 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-13596

Browse the full library · About the Tower of Babel