Randomized Contractions for Multiobjective Minimum Cuts

Authors Hassene Aissi, Ali Ridha Mahjoub, R. Ravi



PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.6.pdf
  • Filesize: 450 kB
  • 13 pages

Document Identifiers

Author Details

Hassene Aissi
Ali Ridha Mahjoub
R. Ravi

Cite AsGet BibTex

Hassene Aissi, Ali Ridha Mahjoub, and R. Ravi. Randomized Contractions for Multiobjective Minimum Cuts. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ESA.2017.6

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 edge-budget constraint, our extension of the randomized contraction method has running time tilde{O}(n^3) in an n-node graph improving upon the best-known 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 edge-budget min cut problem. For the case of (k-1) edge-budget constraints, the extension of our algorithm saves a logarithmic factor from the best-known 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 min-cuts. Our algorithm extends to the node-budget 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 best-known running time by a factor of O(n). For node-budget constrained problems, our improvements arise from incorporating the idea of merging any infeasible super-nodes that arise during the random contraction process. In contrast to cuts excluding a sink, we note that the node-cardinality constrained min-cut problem containing a given source is strongly NP-hard using a reduction from graph bisection.
Keywords
  • minimum cut
  • multiobjective optimization
  • budget constraints
  • graph algorithms
  • randomized algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Amitai Armon and Uri Zwick. Multicriteria global minimum cuts. Algorithmica, 46(1):15-26, 2006. Google Scholar
  2. Maurizio Bruglieri, Francesco Maffioli, and Matthias Ehrgott. Cardinality constrained minimum cut problems: complexity and algorithms. Discrete Applied Mathematics, 137(3):311-341, 2004. Google Scholar
  3. Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2nd edition, 2001. Google Scholar
  4. Matthias Ehrgott. Multicriteria optimization. Springer Science &Business Media, 2006. Google Scholar
  5. Michel X. Goemans and José A. Soto. Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations. SIAM Journal on Discrete Mathematics, 27(2):1123-1145, 2013. Google Scholar
  6. Ara Hayrapetyan, David Kempe, Martin Pál, and Zoya Svitkina. Unbalanced graph cuts. In Algorithms - ESA 2005: 13th Annual European Symposium, Proceedings, pages 191-202, 2005. Google Scholar
  7. D. R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'93, pages 21-30, 1993. Google Scholar
  8. D. R. Karger and C. Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601-640, 1996. Google Scholar
  9. Angsheng Li and Peng Zhang. Unbalanced graph partitioning. In Algorithms and Computation: 21st International Symposium, ISAAC 2010, Proceedings, Part I, pages 218-229, 2010. Google Scholar
  10. Hiroshi Nagamochi and Toshihide Ibaraki. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics, 5(1):54-66, 1992. URL: http://dx.doi.org/10.1137/0405004.
  11. Hiroshi Nagamochi, Kazuhiro Nishimura, and Toshihide Ibaraki. Computing all small cuts in an undirected network. SIAM Journal on Discrete Mathematics, 10(3):469-481. Google Scholar
  12. M. Padberg and G. Rinaldi. An efficient algorithm for the minimum capacity cut problem. Mathematical Programming, 47(1):19-36, 1990. Google Scholar
  13. Maurice Queyranne. Minimizing symmetric submodular functions. Mathematical Programming, 82(1):3-12, 1998. Google Scholar
  14. Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, pages 255-264. ACM, 2008. Google Scholar
  15. Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. Journal of the ACM, 44(4):585-591, 1997. Google Scholar
  16. Rico Zenklusen. Connectivity interdiction. Operations Research Letters, 42(6):450-454, 2014. Google Scholar
  17. Peng Zhang. A new approximation algorithm for the unbalanced min s–t cut problem. Theoretical Computer Science, 609:658-665, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail