Faster Algorithms for Parametric Global Minimum Cut Problems

2019/11/26 by Aissi, Hassene, McCormick, S. Thomas, Queyranne, Maurice
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1911.11847

Abstract

The parametric global minimum cut problem concerns a graph G = (V,E) where the cost of each edge is an affine function of a parameter μ∈ ℝ^d for some fixed dimension d. We consider the problems of finding the next breakpoint in a given direction, and finding a parameter value with maximum minimum cut value. We develop strongly polynomial algorithms for these problems that are faster than a naive application of Megiddo's parametric search technique. Our results indicate that the next breakpoint problem is easier than the max value problem.

Related

• Finding All Global Minimum Cuts In Practice
• Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
• Exact Algorithms for MaxCut on Split Graphs
• Max-Cut Parameterized Above the Edwards-Erdős Bound
• A 0.502⋅MaxCut Approximation using Quadratic Programming