Hypergraph k-cut in randomized polynomial time
Hypergraph k-cut in randomized polynomial time
复制标题
DOI：
10.1007/s10107-019-01443-7
复制
发表时间：
2018-01
影响因子：
2.7
通讯作者：
Karthekeyan Chandrasekaran;Chao Xu;Xilin Yu
中科院分区：
文献类型：
--
作者：
Karthekeyan Chandrasekaran;Chao Xu;Xilin Yu
对于固定整数，超图 k 割问题要求超边的最小子集，其移除导致剩余超图中至少有 k 个连通分量。虽然 graphk-cut 可以有效地解决（Goldschmidt 和 Hochbaum in Math. Oper. Res. 19(1):24–37, 1994），但 hypergraphk-cut 的复杂性是开放的。在这项工作中，我们提出了一种随机多项式时间算法来解决超图割问题。当每个对冲导出的子图具有恒定数量的连接组件时，我们的算法技术可以扩展到解决更一般的对冲切问题。我们的算法基于类似于 Karger 的最小切割算法的随机收缩。我们的主要技术贡献是对冲（超边）的非均匀分布，以便从分布中选择的对冲（超边）的随机收缩成功地以大概率返回最佳解决方案。此外，我们提出了一种基于随机多项式时间逼近的替代收缩方案，用于任意对冲图中的对冲割（即对冲可能具有大量连通分量的对冲图）。我们的算法和分析还限制了各个问题的最佳解决方案的数量。
For a fixed integer, the hypergraphk-cut problem asks for a smallest subset of hyperedges whose removal leads to at leastkconnected components in the remaining hypergraph. While graphk-cut is solvable efficiently (Goldschmidt and Hochbaum in Math. Oper. Res. 19(1):24–37, 1994), the complexity of hypergraphk-cut has been open. In this work, we present a randomized polynomial time algorithm to solve the hypergraphk-cut problem. Our algorithmic technique extends to solve the more general hedgek-cut problem when the subgraph induced by every hedge has a constant number of connected components. Our algorithm is based on random contractions akin to Karger’s min cut algorithm. Our main technical contribution is a non-uniform distribution over the hedges (hyperedges) so that random contraction of hedges (hyperedges) chosen from the distribution succeeds in returning an optimum solution with large probability. In addition, we present an alternative contraction based randomized polynomial time approximation scheme for hedgek-cut in arbitrary hedgegraphs (i.e., hedgegraphs whose hedges could have a large number of connected components). Our algorithm and analysis also lead to bounds on the number of optimal solutions to the respective problems.