The connectivity carcass of a vertex subset in a graph: both odd and even case

Surender Baswana, Abhyuday Pandey · 2025

Read The connectivity carcass of a vertex subset in a graph: both odd and even case by Surender Baswana, Abhyuday Pandey (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-2503-06266.txt.

Introduction

Surender Baswana and Abhyuday Pandey complete a thirty-year-old data structure for graph cuts, in a 2025 paper. Given a set of key vertices, the smallest edge set whose removal splits them is the Steiner mincut. A 1994 design, the connectivity carcass, promised to store all such mincuts compactly.

Proofs for the odd-capacity case landed in 2000, but the even case resisted two decades of attempts. The pair now give a full, self-contained account covering both parities. Their route leans on submodularity, a basic inequality of cut functions, which keeps the argument much simpler. They also show how the structure answers basic mincut queries fast. A long-open gap in graph algorithms is closed.

Catalog record

CREATORSurender Baswana, Abhyuday Pandey
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE171 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-06266

Browse the full library · About the Tower of Babel