The Structure of Minimum Vertex Cuts

2021/02/12 by Pettie, Seth, Yin, Longhui
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2102.06805

Abstract

In this paper we continue a long line of work on representing the cut structure of graphs. We classify the types minimum vertex cuts, and the possible relationships between multiple minimum vertex cuts. As a consequence of these investigations, we exhibit a simple O(κn)-space data structure that can quickly answer pairwise (κ+1)-connectivity queries in a κ-connected graph. We also show how to compute the "closest" κ-cut to every vertex in near linear O(m+poly(κ)n) time.

Related

• Data structure for node connectivity and cut queries
• Near-Optimal Distributed Computation of Small Vertex Cuts
• Complexity and Algorithm for the Matching vertex-cutset Problem
• Minimum Cuts in Near-Linear Time
• The Number of Minimum k-Cuts: Improving the Karger-Stein Bound