IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2015004.html
   My bibliography  Save this paper

Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs

Author

Listed:
  • HASSENE, Aissi
  • MAHJOUB, A. Ridha
  • McCORMICK, S. Thomas
  • QUEYRANNE, Maurice

    (Université catholique de Louvain, CORE, Belgium)

Abstract

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 efficient) 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) non-dominated (Pareto efficient) cuts. These results significantly improve on earlier graph cut results by Mulmuley (1999) and Armon and Zwick (2006). They also imply that the parametric curve and all SND cuts, and, for the bicriteria problems, all Pareto efficient cuts, can be computed in strongly polynomial time when the number of objectives is fixed.

Suggested Citation

  • HASSENE, Aissi & MAHJOUB, A. Ridha & McCORMICK, S. Thomas & QUEYRANNE, Maurice, 2015. "Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs," LIDAM Discussion Papers CORE 2015004, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2015004
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2015.html
    Download Restriction: no
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Samuel Ferey & Pierre Dehez, 2016. "Multiple Causation, Apportionment, and the Shapley Value," The Journal of Legal Studies, University of Chicago Press, vol. 45(1), pages 143-171.
    2. Stephan Helfrich & Arne Herzel & Stefan Ruzika & Clemens Thielen, 2022. "An approximation algorithm for a general class of multi-parametric optimization problems," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1459-1494, October.
    3. Britta Schulze & Kathrin Klamroth & Michael Stiglmayr, 2019. "Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions," Journal of Global Optimization, Springer, vol. 74(3), pages 495-522, July.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2015004. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.