{"ID":2828729,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.12900","arxiv_id":"2512.12900","title":"Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs","abstract":"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~$λ_j$. Let $j$ be the smallest index with $κ(P_j)\\ge k$ and $R := k - κ(P_{j-1})$. We prove a structural decomposition theorem showing that an optimal $k$-cut can be expressed as the level-$(j\\!-\\!1)$ boundary $A_{\\le j-1}$ together with exactly $(R-r)$ \\emph{non-trivial} internal cuts of value at most~$λ_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) = \\widetilde{O}\\left(\\mathrm{poly}(m)+\\Bigl(\\tfrac{n}{λ_j}+n^{ω/3}\\Bigr)^{R}\\right), $$ where $ω\u003c 2.373$ is the matrix multiplication exponent. In particular, if $λ_j \\ge n^{\\varepsilon}$ for some constant $\\varepsilon \u003e 0$, we obtain a \\emph{deterministic sub-$n^k$-time algorithm}, running in $n^{(1-\\varepsilon)(k-1)+o(k)}$ time. Finally, combining our PSP$\\times$KT framework with a small-$λ$ exact subroutine via a simple meta-reduction yields a deterministic $n^{c k+O(1)}$ algorithm for $c = \\max\\{ t/(t+1), ω/3 \\} \u003c 1$, aligning with the exponent in the randomized bound of He--Li (STOC~2022) under the assumed subroutine.","short_abstract":"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~$λ...","url_abs":"https://arxiv.org/abs/2512.12900","url_pdf":"https://arxiv.org/pdf/2512.12900v2","authors":"[\"Mohit Daga\"]","published":"2025-12-15T00:59:17Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}