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
| CREATOR | Yonggang Jiang, Merav Parter, Asaf Petruschka |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 129 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-13596