Abstract
We show that Karger's randomized contraction method (SODA 93) can be adapted to multiobjective global minimum cut problems with a constant number of edge or node budget constraints to give efficient algorithms.
For global minimum cuts with a single edgebudget constraint, our extension of the randomized contraction method has running time tilde{O}(n^3) in an nnode graph improving upon the bestknown randomized algorithm with running time tilde{O}(n^4) due to Armon and Zwick (Algorithmica 2006). Our analysis also gives a new upper bound of O(n^3) for the number of optimal solutions for a single edgebudget min cut problem. For the case of (k1) edgebudget constraints, the extension of our algorithm saves a logarithmic factor from the bestknown randomized running time of O(n^{2k} log^3 n). A main feature of our algorithms is to adaptively choose, at each step, the appropriate cost function used in the random selection of edges to be contracted.
For the global min cut problem with a constant number of node budgets, we give a randomized algorithm with running time tilde{O}(n^2), improving the current best determinisitic running time of O(n^3) due to Goemans and Soto (SIAM Journal on Discrete Mathematics 2013). Our method also shows that the total number of distinct optimal solutions is bounded by O(n^2) as in the case of global mincuts. Our algorithm extends to the nodebudget constrained global min cut problem excluding a given sink with the same running time and bound on number of optimal solutions, again improving upon the bestknown running time by a factor of O(n). For nodebudget constrained problems, our improvements arise from incorporating the idea of merging any infeasible supernodes that arise during the random contraction process.
In contrast to cuts excluding a sink, we note that the nodecardinality constrained mincut problem containing a given source is strongly NPhard using a reduction from graph bisection.
BibTeX  Entry
@InProceedings{aissi_et_al:LIPIcs:2017:7868,
author = {Hassene Aissi and Ali Ridha Mahjoub and R. Ravi},
title = {{Randomized Contractions for Multiobjective Minimum Cuts}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {6:16:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7868},
URN = {urn:nbn:de:0030drops78686},
doi = {10.4230/LIPIcs.ESA.2017.6},
annote = {Keywords: minimum cut, multiobjective optimization, budget constraints, graph algorithms, randomized algorithms}
}
Keywords: 

minimum cut, multiobjective optimization, budget constraints, graph algorithms, randomized algorithms 
Collection: 

25th Annual European Symposium on Algorithms (ESA 2017) 
Issue Date: 

2017 
Date of publication: 

01.09.2017 