论文标题
HyperGraph $ k $ - 用于确定性多项式时间的固定$ k $
Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time
论文作者
论文摘要
我们考虑HyperGraph- $ k $ - 切口问题。该输入由一个HyperGraph $ g =（v，e）$，其中包括非阴性HyperEdge-Costs $ C：E \ Rightarrow r _+$和一个正整数$ K $。目的是找到一个至少成本的子集$ f \ subseteq e $，以使$ g-f $中的连接组件的数量至少为$ k $。目标的另一种公式是将$ v $的分区划分为$ k $ non-non-nter-non-nter-sets $ v_1，v_2，\ ldots，v_k $，以最大程度地降低穿越分区的超越的成本。 Graph-$ k $ -cut是通过限制图表输入获得的HyperGraph- $ K $ cut的特殊情况。几种不同的方法会导致固定$ k $时的多项式时间算法-Cut-$ k $ - 从Goldschmidt和Hochbaum（1988）的工作开始。相比之下，直到最近，开发了用于超图$ k $ cut的随机多项式时间算法（Chandrasekaran，Xu，Yu，Yu，2018），通过对Karger的图形随机收缩方法的细微概括。在这项工作中，我们为所有固定$ k $的HyperGraph-$ k $ cut开发了第一个确定性的多项式时间算法。我们描述了两种算法，这两种算法都是基于分歧和征服方法。第一种算法更简单，并以$ n^{o（k^2）} $时间运行，而第二个则以$ n^{o（k）} $时间运行。我们的证明依靠新的结构结果，可以通过解决最低$（S，T）$ - 终端切割来有效回收最佳$ K $ - 分区的零件。我们的技术即使对于图形为$ k $ - cut，也为新见解提供了新的见解。
We consider the Hypergraph-$k$-cut problem. The input consists of a hypergraph $G=(V,E)$ with non-negative hyperedge-costs $c: E\rightarrow R_+$ and a positive integer $k$. The objective is to find a least-cost subset $F\subseteq E$ such that the number of connected components in $G-F$ is at least $k$. An alternative formulation of the objective is to find a partition of $V$ into $k$ non-empty sets $V_1,V_2,\ldots,V_k$ so as to minimize the cost of the hyperedges that cross the partition. Graph-$k$-cut, the special case of Hypergraph-$k$-cut obtained by restricting to graph inputs, has received considerable attention. Several different approaches lead to a polynomial-time algorithm for Graph-$k$-cut when $k$ is fixed, starting with the work of Goldschmidt and Hochbaum (1988). In contrast, it is only recently that a randomized polynomial time algorithm for Hypergraph-$k$-cut was developed (Chandrasekaran, Xu, Yu, 2018) via a subtle generalization of Karger's random contraction approach for graphs. In this work, we develop the first deterministic polynomial time algorithm for Hypergraph-$k$-cut for all fixed $k$. We describe two algorithms both of which are based on a divide and conquer approach. The first algorithm is simpler and runs in $n^{O(k^2)}$ time while the second one runs in $n^{O(k)}$ time. Our proof relies on new structural results that allow for efficient recovery of the parts of an optimum $k$-partition by solving minimum $(S,T)$-terminal cuts. Our techniques give new insights even for Graph-$k$-cut.
