论文标题
多准则削减和尺寸约束的$ k $ cuts in Hypergraphs
Multicritera Cuts and Size-Constrained $k$-cuts in Hypergraphs
论文作者
论文摘要
我们解决多标准全球最小切割和大小约束最小$ k $ cut的计数和优化变体。 1。对于具有$ t $ HyperEDGE-COST功能的$ r $ -rank $ n $ n $ vertex HyperGraph，我们表明多目标min-cuts的数量为$ O（r2^{tr} n^{3t-1}）$。特别是，这表明，恒定标准数量的恒定等级超图中的参数最小剪辑数量强烈多项式，因此解决了AISSI，Mahjoub，Mahjoub，McCormick和Queyranne的空旷问题（Math Programing，2015年）。此外，我们给出随机算法，以强烈的多项式时间列举所有多物镜最小切割和所有帕累托最佳切割。 2。我们还解决了节点预算的多目标min-min-cuts：对于具有$ t $ t $ tugtex-pertex-weight函数的$ n $ vertex超图，我们表明，节点预先计算的多目标min-cuts $ o（r2^{r2^{r} n^{r} n^{t+2}）$，是$ r的排名$ b $ -MultiObjective Min-Cuts用于固定预算矢量$ b $是$ O（n^2）$。 3。我们表明，对于恒定$ k $，在多项式时间内可以解决零件大小的恒定下限的最小值$ k $ - 零件，从而解决了Queyranne提出的一个开放问题。我们的技术还表明，最佳解决方案的数量是多项式。 我们所有的结果都基于卡格的随机收缩方法（Soda，1993）。我们的技术说明了关于多物原理的最小切割和尺寸约束的$ k $ cuts的随机收缩方法的多功能性，以解决计数和算法问题。
We address counting and optimization variants of multicriteria global min-cut and size-constrained min-$k$-cut in hypergraphs. 1. For an $r$-rank $n$-vertex hypergraph endowed with $t$ hyperedge-cost functions, we show that the number of multiobjective min-cuts is $O(r2^{tr}n^{3t-1})$. In particular, this shows that the number of parametric min-cuts in constant rank hypergraphs for a constant number of criteria is strongly polynomial, thus resolving an open question by Aissi, Mahjoub, McCormick, and Queyranne (Math Programming, 2015). In addition, we give randomized algorithms to enumerate all multiobjective min-cuts and all pareto-optimal cuts in strongly polynomial-time. 2. We also address node-budgeted multiobjective min-cuts: For an $n$-vertex hypergraph endowed with $t$ vertex-weight functions, we show that the number of node-budgeted multiobjective min-cuts is $O(r2^{r}n^{t+2})$, where $r$ is the rank of the hypergraph, and the number of node-budgeted $b$-multiobjective min-cuts for a fixed budget-vector $b$ is $O(n^2)$. 3. We show that min-$k$-cut in hypergraphs subject to constant lower bounds on part sizes is solvable in polynomial-time for constant $k$, thus resolving an open problem posed by Queyranne. Our technique also shows that the number of optimal solutions is polynomial. All of our results build on the random contraction approach of Karger (SODA, 1993). Our techniques illustrate the versatility of the random contraction approach to address counting and algorithmic problems concerning multiobjective min-cuts and size-constrained $k$-cuts in hypergraphs.
