Hypergraph k-cut for fixed k in deterministic polynomial time
share
We consider the Hypergraph-k-cut problem. The input consists of a hypergraph G=(V,E) with non-negative hyperedge-costs c: E→ R_+ and a positive integer k. The objective is to find a least-cost subset F⊆ 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,…,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.
READ FULL TEXT