A new contraction technique with applications to congruency-constrained cuts
Open access
Date
2020-09Type
- Journal Article
Abstract
Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global mininmum cuts, minimum s–t cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to r modulo m, for some integers r and m. Apart from being a natural generalization of odd cuts, congruency-constrained minimum cuts exhibit an interesting link to a long-standing open problem in Integer Programming, namely whether integer programs described by an integer constraint matrix with bounded subdeterminants can be solved efficiently. We develop a new contraction technique inspired by Karger’s celebrated contraction algorithm for minimum cuts, which, together with further insights, leads to a polynomial time randomized approximation scheme for congruency-constrained minimum cuts for any constant modulus m. Instead of contracting edges of the original graph, we use splitting-off techniques to create an auxiliary graph on a smaller vertex set, which is used for performing random edge contractions. This way, a well-structured distribution of candidate pairs of vertices to be contracted is obtained, where the involved pairs are generally not connected by an edge. As a byproduct, our technique reveals new structural insights into near-minimum odd cuts, and, more generally, near-minimum congruency-constrained cuts. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000412160Publication status
publishedExternal links
Journal / series
Mathematical ProgrammingVolume
Pages / Article No.
Publisher
SpringerSubject
Minimum cuts; Congruency-constrained optimization; Contraction algorithm; Splitting offOrganisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Funding
165866 - New Approaches to Constrained Submodular Maximization (SNF)
184622 - Toward Stronger Approximation Algorithms for Fundamental Network Design and Optimization Problems (SNF)
Related publications and datasets
More
Show all metadata