User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Strongly Polynomial Bounds for Multiobjective and Parametric Global minimum Cuts in Graphs and Hypergraphs

Primary tabs

Aissi, Hassene [PSl, LAMSADE, Université Paris-Dauphine, Paris, France] Ridha Mahjoub, A. [PSl, LAMSADE, Université Paris-Dauphine, Paris, France] McCormick, S. Thomas [Sauder School of Business at the University of Britissh Columbia, Vancouver, BC, Canada] Queyranne, Maurice [Sauder School of Business at the University of Britissh Columbia, Vancouver, BC, Canada - CORE, Université Catholique de Louvain, Belgium]

We consider multiobjective and parametric versions of the global minimum cut problem in undirected graphs and bounded-rank hypergraphs with multiple edge cost functions. For a fixed number of edge cost functions, we show that the total number of supported non-dominated (SND) cuts is bounded by a polynomial in the numbers of nodes and edges, i.e., is strongly polynomial. This bound also applies to the combinatorial facet complexity of the problem, i.e., the maximum number of facets (linear pieces) of the parametric curve for the parametrized (linear combination) objective, over the set of all parameter vectors such that the parametrized edge costs are nonnegative and the parametrized cut costs are positive. We sharpen this bound in the case of two objectives (the bicriteria problem), for which we also derive a strongly polynomial upper bound on the total number of non-dominated (Pareto optimal) cuts. In particular, the bicriteria global minimum cut problem in an n-node graph admits O(n3 log n) SND cuts and O(n5 log n) Pareto optimal cuts. These results significantly improve on earlier graph cut results by Mulmuley (SIAM J Comput 28(4):1460– 1509, 1999) and Armon and Zwick (Algorithmica 46(1):15–26, 2006). They also imply that the parametric curve and all SND cuts, and, for the bicriteria problems, all Pareto optimal cuts, can be computed in strongly polynomial time when the number of objectives is fixed.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès interdit
Publication date 2015
Language Anglais
Journal information "Mathematical Programming" - Vol. 154, no.1, p. 3-28 (2015)
Publisher Springer-Verlag (Berlin Heidelberg)
issn 0025-5610
e-issn 1436-4646
Publication status Publié
Affiliation UCL - SSH/LIDAM/CORE - Center for operations research and econometrics
Keywords Multiobjective optimization ; Parametric optimization ; Global minimum cut
Links
  1. Aissi Hassene, Mahjoub A. Ridha, McCormick S. Thomas, Queyranne Maurice, A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts, Integer Programming and Combinatorial Optimization (2014) ISBN:9783319075563 p.25-36, 10.1007/978-3-319-07557-0_3
  2. Armon Amitai, Zwick Uri, Multicriteria Global Minimum Cuts, 10.1007/s00453-006-0068-x
  3. Carstensen Patricia J., Complexity of some parametric integer and network programming problems, 10.1007/bf02591893
  4. Chan T. M., Output-sensitive results on convex hulls, extreme points, and related problems, 10.1007/bf02712874
  5. Chekuri, C., Korula, N.: Personal Communication (2010). Cited in: T. Fukunaga. Computing minimum multiway cuts in hypergraphs from hypertree packings. In: Integer Programming and Combinatorial Optimization (IPCO 2010), Springer LNCS 6080, pp. 15–28 (2010)
  6. Dinitz, E.A., Karzanov, A.V., Lomonosov, M.V.: On the structure of the system of minimum edge cuts in a graph. In: Fridman, A.A. (ed.) Issledovaniya po Diskretnoi Optimizatsii (Studies in Discrete Optimization), pp. 290–306. Nauka Publishers, Moscow (1976)
  7. Downey R. G., Fellows M. R., Parameterized Complexity, ISBN:9781461267980, 10.1007/978-1-4612-0515-9
  8. Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2005)
  9. Eisner Mark J., Severance Dennis G., Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases, 10.1145/321978.321982
  10. Fernández-Baca, D., Venkatachalam, B.: Sensitivity analysis in combinatorial optimization, chapter 30. In: Gonzalez, T. (ed.) Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC Press, Boca Raton (2007)
  11. Fernández-Baca David, Seppäläinen Timo, Slutzki Giora, Parametric multiple sequence alignment and phylogeny construction, 10.1016/s1570-8667(03)00078-9
  12. Hamacher H. W., Queyranne M., K best solutions to combinatorial optimization problems, 10.1007/bf02022039
  13. Hamacher H.W., Picard J.-C., Queyranne M., Ranking the Cuts and Cut-Sets of a Network, Algebraic and Combinatorial Methods in Operations Research, Proceedings of the Workshop on Algebraic Structures in Operations Research (1984) ISBN:9780444875716 p.183-200, 10.1016/s0304-0208(08)72962-1
  14. Henzinger Monika, Williamson David P., On the number of small cuts in a graph, 10.1016/0020-0190(96)00079-8
  15. Ihler Edmund, Wagner Dorothea, Wagner Frank, Modeling hypergraphs by graphs with the same mincut properties, 10.1016/0020-0190(93)90115-p
  16. Karger, D.R.: Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In: Proceedings on Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 21–30 (1993)
  17. Karger David R., Minimum cuts in near-linear time, 10.1145/331605.331608
  18. Karger David R., Panigrahi Debmalya, A Near-Linear Time Algorithm for Constructing a Cactus Representation of Minimum Cuts, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (2009) ISBN:9780898716801 p.246-255, 10.1137/1.9781611973068.28
  19. Karger David R., Stein Clifford, A new approach to the minimum cut problem, 10.1145/234533.234534
  20. Klimmek, R., Wagner, F.: A simple hypergraph min cut algorithm. Technical Report b 96-02, Inst. of Computer Science, Freie Universität Berlin (1996)
  21. Kogan, D., Krauthgamer, R.: Sketching cuts in graphs and hypergraphs. arXiv preprint arXiv:1409.2391 (2014)
  22. Lawler Eugene L., A Procedure for Computing theKBest Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem, 10.1287/mnsc.18.7.401
  23. Lawler E. L., Cutsets and partitions of hypergraphs, 10.1002/net.3230030306
  24. Loff Barreto, B.S.: A medley for computational complexity: with applications of information theory, learning theory, and ketan mulmuley’s parametric complexity technique. PhD thesis, University of Amsterdam (2014)
  25. Mak Wai-Kei, Wong D.F., A fast hypergraph min-cut algorithm for circuit partitioning, 10.1016/s0167-9260(00)00008-0
  26. Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Upper Saddle River (1994)
  27. Mulmuley Ketan, Parallel vs. parametric complexity, Lecture Notes in Computer Science (1997) ISBN:9783540633075 p.282-283, 10.1007/3-540-63307-3_67
  28. Mulmuley Ketan, Lower Bounds in a Parallel Model without Bit Operations, 10.1137/s0097539794282930
  29. Murty Katta G., Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost, 10.1287/opre.16.3.682
  30. Nagamochi Hiroshi, Ibaraki Toshihide, Computing Edge-Connectivity in Multigraphs and Capacitated Graphs, 10.1137/0405004
  31. Nagamochi Hiroshi, Ibaraki Toshihide, Algorithmic Aspects of Graph Connectivity, ISBN:9780511721649, 10.1017/cbo9780511721649
  32. Nagamochi, H., Nakamura, S., Ishii, T.: Constructing a cactus for minimum cuts of a graph in $$O(mn+n^2 \log n)$$ O ( m n + n 2 log n ) space. IEICE Trans. Inf. Syst. E86-D, 179–185 (2003)
  33. Nagamochi Hiroshi, Nishimura Kazuhiro, Ibaraki Toshihide, Computing All Small Cuts in an Undirected Network, 10.1137/s0895480194271323
  34. Papadimitriou C.H., Yannakakis M., On the approximability of trade-offs and optimal access of Web sources, 10.1109/sfcs.2000.892068
  35. Panigrahi, D.: Optimization problems in network connectivity. Ph.D. thesis, MIT (2012)
  36. Preparata Franco P., Shamos Michael Ian, Computational Geometry, ISBN:9781461270102, 10.1007/978-1-4612-1098-6
  37. Queyranne, M.: Minimizing symmetric submodular functions. Math. Program. 82(1–2), 3–12 (1998)
  38. Queyranne, M., Guiñez, F.: On optimum k-way partitions with submodular costs and minimum part-size constraints. In: Talk given at the Workshop on Modern Aspects of Submodularity, Georgia Institute of Technology, Atlanta (GA) USA, March 21 (2012)
  39. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Hoboken (1998)
  40. Seidel Raimund, The upper bound theorem for polytopes: an easy proof of its asymptotic version, 10.1016/0925-7721(95)00013-y
  41. Steiner J., Einige Gesetze über die Theilung der Ebene und des Raumes., 10.1515/crll.1826.1.349
  42. Stoer Mechthild, Wagner Frank, A simple min-cut algorithm, 10.1145/263867.263872
  43. Vazirani Vijay V., Yannakakis Mihalis, Suboptimal cuts: Their enumeration, weight and number, Automata, Languages and Programming (1992) ISBN:9783540557197 p.366-377, 10.1007/3-540-55719-9_88
  44. Hannah Honghua Yang, Wong D.F., Balanced partitioning, 10.1109/43.552086
  45. Zimmerman Seth, Slicing Space, 10.2307/2687119
Bibliographic reference Aissi, Hassene ; Ridha Mahjoub, A. ; McCormick, S. Thomas ; Queyranne, Maurice. Strongly Polynomial Bounds for Multiobjective and Parametric Global minimum Cuts in Graphs and Hypergraphs. In: Mathematical Programming, Vol. 154, no.1, p. 3-28 (2015)
Permanent URL http://hdl.handle.net/2078.1/175687