Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time

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. Graphk-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) [12,13]. In contrast, it is only recently that a randomized polynomial time algorithm for Hypergraph-k-Cut was developed [2] 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.