Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs

We present a \emph{deterministic exact algorithm} for the \emph{minimum $k$-cut problem} on simple graphs. Our approach combines the \emph{principal sequence of partitions (PSP)}, derived canonically from ideal loads, with a single level of \emph{Kawarabayashi–Thorup (KT)} contractions at the critical PSP threshold~${\lambda }_j$. Let $j$ be the smallest index with $\kappa (P_j)\ge k$ and $R:=k-\kappa (P_{j-1})$. We prove a structural decomposition theorem showing that an optimal $k$-cut can be expressed as the level-$(j\text{\hspace{0.17em}⁣}-\text{\hspace{0.17em}⁣}1)$ boundary $A_{\le j-1}$ together with exactly $(R-r)$ \emph{non-trivial} internal cuts of value at most~${\lambda }_j$ and $r$ \emph{singleton isolations} (islands'') inside the parts of~$P_{j-1}$. At this level, KT contractions yield kernels of total size $\widetilde{O}(n / λ_j)$, and from them we build a \emph{canonical border family}~$\mathcal{B}$ of the same order that deterministically covers all optimal refinement choices. Branching only over~$\mathcal{B}$ (and also including an explicit island’’ branch) gives total running time $$T(n,m,k)=\tilde{O}(\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(m)+(\frac{n}{{\lambda }_j}+n^{\omega \mathrm{/}3}{)}^R),$$ where $\omega <2.373$ is the matrix multiplication exponent. In particular, if ${\lambda }_j\ge n^{\epsilon }$ for some constant $\epsilon >0$, we obtain a \emph{deterministic sub-$n^k$-time algorithm}, running in $n^{(1-\epsilon )(k-1)+o(k)}$ time. Finally, combining our PSP$\times$KT framework with a small-$\lambda$ exact subroutine via a simple meta-reduction yields a deterministic $n^{ck+O(1)}$ algorithm for $c=\max \{t\mathrm{/}(t+1),\omega \mathrm{/}3\}<1$, aligning with the exponent in the randomized bound of He–Li (STOC~2022) under the assumed subroutine.