2025/12/15 by Mohit Daga, Daga, Mohit
Computer Science · Engineering · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2512.12900
openalex publication_date 2025/12/15 · openalex created_date 2025/12/17 · openalex updated_date 2026/07/28
We present a deterministic exact algorithm for the minimum k-cut problem on simple graphs. Our approach combines the principal sequence of partitions (PSP), derived canonically from ideal loads, with a single level of Kawarabayashi--Thorup (KT) contractions at the critical PSP threshold~λj. Let j be the smallest index with κ(Pj)≥ k and R := k - κ(Pj-1). We prove a structural decomposition theorem showing that an optimal k-cut can be expressed as the level-(j - 1) boundary A≤ j-1 together with exactly (R-r) non-trivial internal cuts of value at most~λj and r singleton isolations (``islands'') inside the parts of~Pj-1. At this level, KT contractions yield kernels of total size \widetildeO(n / λj), and from them we build a canonical border family~B of the same order that deterministically covers all optimal refinement choices. Branching only over~B (and also including an explicit ``island'' branch) gives total running time T(n,m,k) = \widetildeO(poly(m)+(\tfracnλj+nω/3)R), where ω< 2.373 is the matrix multiplication exponent. In particular, if λj ≥ nε for some constant ε > 0, we obtain a deterministic sub-nk-time algorithm, running in n(1-ε)(k-1)+o(k) time. Finally, combining our PSP×KT framework with a small-λ exact subroutine via a simple meta-reduction yields a deterministic nc k+O(1) algorithm for c = max\ t/(t+1), ω/3 \ < 1, aligning with the exponent in the randomized bound of He--Li (STOC~2022) under the assumed subroutine.