A new contraction technique with applications to congruency-constrained cuts
- PDF / 511,800 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 79 Downloads / 161 Views
Series B
A new contraction technique with applications to congruency-constrained cuts Martin Nägele1 · Rico Zenklusen1 Received: 31 May 2019 / Accepted: 23 March 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
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. Keywords Minimum cuts · Congruency-constrained optimization · Contraction algorithm · Splitting off
A short version of this paper appeared at IPCO 2019. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 817750). This work was supported by Swiss National Science Foundation Grants 200021_165866 and 200021_184622. Extended author information available on the last page of the article
123
M. Nägele, R. Zenklusen
Mathematics Subject Classification 90C27 · 90C35 · 68R05 · 68Q25 · 05C99
1 Introduction Cuts in undirected graphs are a basic structure in Combinatorial Optimization with a multitude of applications. The global minimum cut problem, the minimum s–t cut problem, and the minimum odd cut problem are among the best known efficiently solvable minimum cut variants, and have been the cradle of many exciting algorithmic techniques. We study a generalization of these problems that we call congruencyconstrained minimum cut (CCMC), where a congruency constraint on the vertices in the cut is imposed, as described in the box below.1 Congruency-Constrained Min
Data Loading...
