We investigate the bicriteria global minimum cut problem where each edge is evaluated by two nonnegative cost functions. The parametric complexity of such a problem is the number of linear segments in the parametric curve when we take all convex combinations of the criteria. We prove that the parametric complexity of the global minimum cut problem is O(|V|~3). As a consequence, we show that the number of non-dominated points is O(|V|~7) and give the first strongly polynomial time algorithm to compute these points. These results improve on significantly the super-polynomial bound on the parametric complexity given by Mulmuley, and the pseudo-polynomial time algorithm of Armon and Zwick to solve this bicriteria problem. We extend some of these results to arbitrary cost functions and more than two criteria, and to global minimum cuts in hypergraphs.
展开▼
机译：我们研究双标准全局最小割问题，其中每个边由两个非负成本函数评估。当我们采用标准的所有凸组合时，此问题的参数复杂度是参数曲线中线性段的数量。我们证明全局最小割问题的参数复杂度为O（| V |〜3）。结果，我们证明了非支配点的数量为O（| V |〜7），并给出了第一个强多项式时间算法来计算这些点。这些结果显着改善了Mulmuley给出的参数复杂度的超多项式边界，以及Armon和Zwick的伪多项式时间算法来解决该双标准问题。我们将其中一些结果扩展到任意成本函数和两个以上的标准，并扩展到超图的全局最小割减。
展开▼
