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

• 成果类型: Article
• 署名作者: Aissi, Hassene; Mahjoub, A. Ridha; McCormick, S. Thomas; Queyranne, Maurice
• 署名单位: Universite PSL; Universite Paris-Dauphine; University of British Columbia; Universite Catholique Louvain
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0944-8
• 发表日期: 2015
• 页码: 3-28
• 关键词: algorithm

摘要

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 SND cuts and 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.