  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.
