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

Aissi Hassene, A. Ridha Mahjoub, S. Thomas McCORMICK and Maurice Queyranne ()
Additional contact information
Maurice Queyranne: Université catholique de Louvain, CORE, Belgium

No 2015004, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Date: 2015-01-01
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2015.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2015004

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().