Approximate minimum cuts and their enumeration

2022/11/30 by Beideman, Calvin, Chandrasekaran, Karthekeyan, Wang, Weihang · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2211.16747

Abstract

We show that every α-approximate minimum cut in a connected graph is the unique minimum (S,T)-terminal cut for some subsets S and T of vertices each of size at most \lfloor2α\rfloor+1. This leads to an alternative proof that the number of α-approximate minimum cuts in a n-vertex connected graph is n^O(α) and they can all be enumerated in deterministic polynomial time for constant α.

Cited by

• Constrained Cuts, Flows, and Lattice-Linearity
• Almost Tight Additive Guarantees for k-Edge-Connectivity

Related

• Fixed-parameter tractability of counting small minimum (S,T)-cuts
• The Structure of Minimum Vertex Cuts
• The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
• A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals
• A note on small cuts for a terminal