Faster Minimum k-Cut II: Near-Optimal and Deterministic for Weighted Graphs

Conditional lower bound and prior work

• Under the Max-Weight Clique conjecture, weighted Minimum k-Cut requires n^(k−1−o(1)) time for every fixed k.The previous randomized bound was n^(k−2)(m+n)(log n)^O(k^2), giving eO(nm) for k=3.Source: §1 · p. 3

Our results

• Weighted Minimum 3-Cut takes O(n^2 log^2 n) randomized time and eO(n^2) deterministic time.Source: §1 · p. 3
• For fixed k ≥3, the algorithms run in k^O(k^2)n^(k−1) log^2 n randomized time or k^O(k^2)n^(k−1) log^O(1) n deterministic time.The randomized bound holds with high probability.Source: §1 · p. 3

A faster algorithm for 3-cut

• After strict-small and two-light-side cases are handled, the remaining 3-cut optimum has a unique medium side to complete.A strict-small side has boundary below λ3/2; a light side has boundary at most 2λ3/3.Source: §1 · p. 3
• Tree packing samples O(log n) spanning trees, enumerates each tree’s two-edge-respecting cuts, and retains O(n) lightest candidates per tree.A lost relevant optimum side is certified by a crossing among retained cuts.Source: §1 · p. 3
• For each candidate medium side, the completion reduces to a residual-tree 2-respecting cut or direct enumeration, with repair edges handling the hardest crossing pattern.The 2-respecting optimizer’s graph-dependent preprocessing is reused across O(n) candidate sides, enabling eO(m+n^2) batched time.Source: §1 · p. 4

Reducing k-cut to 3-cut

• The k-cut reduction recursively completes both sides of each candidate light cut; if truncation discards the relevant side, an overflow certificate yields an optimum k-cut directly.For the randomized reduction, sampled trees provide (k−1)-respecting candidates, truncated using constructive light-cut bounds.Source: §1 · p. 4

Derandomization

• Derandomization uses a near-minimum-cut skeleton for 3-cut and, for the reduction, a specialized 4-cut algorithm plus spectral sparsification for k ≥5.The 4-cut method branches on safe contractions when its quotient minimum cut is below one third of the optimum; for k ≥5 it enumerates cuts from the full dual tree-packing support.Source: §1 · pp. 4–5

Cuts and partitions

• A rooted cut is the side of a cut not containing the fixed root, while a partition refines another when each of its parts lies within one part of the other.Source: §2 · p. 5

Minimum k-cut

• A k-cut partitions the graph into exactly k nonempty sides, and λk denotes the minimum cut value; the equivalent edge-removal formulation allows at least k components.Source: §2 · p. 5

Tree-respecting cuts

• A cut p-respects a tree when its boundary uses at most p tree edges; a rooted p-respecting side is represented by the symmetric difference of the corresponding rooted subtrees.Source: §2 · p. 6

Cut-value regimes

• For a threshold U, a cut is U-light at boundary at most 2U/k, U-small at most U/(k−1), and U-medium between those bounds.When U=λk, the threshold is omitted from the terminology.Source: §2 · p. 6

2-respecting cut optimization

• The algorithm uses the fixed-tree 2-respecting minimum-cut optimizer of [GMW21], with range-counting queries on a bounded-degree binary expansion of the tree.Auxiliary vertices in the expansion support data structures but do not represent graph vertices.Source: §3 · p. 6
• The optimizer finds a minimum cut crossing at most two distinguished tree edges in O(n(Q+1) log n) time and O(n log n) space.The tree edges need not belong to the input graph.Source: §3 · p. 6
• For a fixed tree edge, cross-interested and down-interested edges form root-to-node paths, whose endpoints and mutually interested pairs can be found using centroid searches and sorting.The resulting interest-list construction takes O(n log n) time; the Monge searches use O(nQ log n) time.Source: §3 · p. 7

3.1 Strict-Small Cuts

• Two crossing cuts each of value at most 2U/k yield a k-cut of value at most U when k is 3 or 4.Source: §3.1 · p. 7
• If an optimum 3-cut has a strict-small side, the global minimum-cut bipartition identifies that side and induced minimum-cut computations complete an optimum 3-cut.The resulting candidate Psmall is guaranteed to have value λ3.Source: §3.1 · p. 8
• Under the condition cG(Psmall) > λ, the comparison gives λ < 3μ; the structural argument also establishes x > μ/3, cG(D) < 3μ, and cG(A) < 2μ.Source: §3.1 · p. 8

3.2 Respecting Cuts and Capacity Matrices

• A rooted cut p-respects a tree exactly when it is the symmetric difference of at most p rooted subtrees, with a unique representation from its crossing tree edges.Source: §3.2 · p. 9
• The capacity matrix uses DFS order and two-dimensional prefix sums to answer capacities between constant-interval sets in O(1) time after O(m+n^2) preprocessing.Source: §3.2 · p. 9
• After capacity-matrix construction, the M lightest rooted cuts crossing at most p tree edges can be enumerated in p^O(1)n^p time.For p=2, the total time including matrix construction is O(m+n^2).Source: §3.2 · p. 9

3.3 Sampling Trees from a Random Skeleton

• With high probability, the random skeleton approximates every cut within a factor of 1 ± ε, has O(mε^-2 log n) edge copies, and can be stored in O(m) space.Every spanning tree of the skeleton is also a spanning tree of the original graph's underlying graph.Source: §3.3 · p. 10
• The near-optimal fractional tree packing has support O(ε^-2η^-2 log^2 n) and is constructed in O(mε^-2η^-2 log^2 n) randomized time with probability 1 − e^-Ω(m).Its value is at least (1 − η) times the maximum fractional spanning-tree-packing value.Source: §3.3 · p. 10
• A fixed light optimum side is 2-respected by a sampled tree with probability greater than 1/8 for ε = η = 1/100.Here light means boundary at most 2λ/3.Source: §3.3 · p. 11
• A good tree excludes the difficult degree patterns (1, 3, 4) and (1, 4, 3), yielding probability greater than 1/16 for the unique-medium-side optimum.The residual B–C cut's complexity matters after fixing A; its tree edges receive greater weight because they survive removing A.Source: §3.3 · pp. 11–12
• With O(log n) independent tree samples, with high probability every light optimum side is 2-respected by some tree and a unique-medium-side optimum has a good tree.The simultaneous guarantee applies to any fixed optimum 3-cut.Source: §3.3 · p. 12

3.4 Selecting the Relevant Light Cuts

• For each sampled tree, retain its 2n + 1 lightest nonempty rooted cuts that 2-respect it, then deduplicate and keep the globally lightest 2n + 1 distinct cuts.The family is ordered by boundary value with deterministic tie-breaking.Source: §3.4 · p. 13
• Binary search finds the longest laminar prefix; if it is not the full family, a crossing pair yields a 3-cut of value at most 3B/2.B is the boundary of the last cut in the prefix ending at the first omitted cut.Source: §3.4 · p. 13
• With high probability, any light optimum side is either represented in the laminar family or the crossing-pair construction produces an optimum 3-cut.The crossing 3-cut has value λ when the side is not represented.Source: §3.4 · p. 13

3.5 Eliminating Two-Light-Side Optima

• The rooted cuts in the laminar family form either disjoint or nested pairs, and their induced three-partition values are computed by subtracting the duplicated edge class.A prefix table evaluates each pair in O(1) time, and the algorithm scans all O(n^2) pairs.Source: §3.5 · p. 13
• If an optimum has at least two sides of boundary at most 2λ/3, with high probability either the crossing-pair cut or the pair scan is optimal.When both rooted orientations belong to the laminar family, their corresponding pair gives exactly the three optimum parts.Source: §3.5 · p. 14
• After the strict-small and two-light-side cases fail, the remaining optimum has a unique light side A with λ/2 ≤ cG(A) ≤ 2λ/3, while the other sides exceed 2λ/3.The algorithm processes both sides of each stored rooted cut, so A is a candidate whenever its rooted cut is in the laminar family.Source: §3.5 · p. 14

3.6 Tree Components and Good-Tree Patterns

• For any nontrivial A in a tree, the numbers of components induced by A and its complement sum to dA + 1.Contracting each component on either side gives a tree with dA edges.Source: §3.6 · p. 14
• For a good tree, if dA is 1 or 2, the residual optimum crosses at most two surviving tree edges; if dA ≥ 3, it crosses at most one.When dA = 2 and T[A] is connected, T \ A has two components; when T[A] is disconnected, T \ A is connected.Source: §3.6 · p. 14

3.7 Virtual Links for Connected Two-Respecting Sides

• When dA = 2 and T[A] is connected, adding a zero-capacity link between the two components of T \ A creates the virtual-link tree.The added link need not be an edge of G.Source: §3.7 · p. 14
• The virtual link covers residual cuts for h ≤ 3 and the (2, 2, 4) and (2, 4, 2) patterns when h = 4; only (2, 3, 3) remains uncovered.In the h = 4 covered patterns, the residual cut crosses its two surviving tree edges and not the virtual link.Source: §3.7 · pp. 14–15

3.8 Deterministic Rectangle Nets

• O(ε^-2) selected points hit every axis-aligned rectangle containing at least εW weight; unions of q rectangles are covered by replacing ε with ε/q.The construction uses O(ε^-2 log N) rectangle-weight queries.Source: §3.8 · p. 15
• The net partitions the first coordinate into O(1/ε) slabs, then selects support points at weighted quantiles in each slab to ensure coverage.For a rectangle of weight at least εW, a contained slab contributes at least εW/(2s) within its second-coordinate range.Source: §3.8 · p. 15

3.9 Repair Edges for the (2, 3, 3) Pattern

• For optimum (A, B, C), a repair edge joins endpoints in the same one of B or C; adding it to T \\ A forms a spanning tree of G \\ A, where the residual optimum crosses exactly its two original B–C tree edges.Source: §3.9 · p. 15
• The constant-fraction repair capacity follows because splitting an optimum side across T \ A leaves substantial same-side capacity connecting its fragments.The whole side has boundary below 5λ/6, while its fragments, except for a possible strict-small piece, each have boundary at least λ/2.Source: §3.9 · p. 16
• When A is the unique medium side and T[A] is connected with degree pattern (2, 3, 3), repair edges carry more than one tenth of c(FA,T).The repair-edge capacity is established to exceed λ/18; the eligible edges have capacity bounded by the repair capacity plus at most λ/2 of B–C edges.Source: §3.9 · pp. 16–17
• A deterministic set of at most b endpoint pairs, constructible in O(log n) time, contains a repair edge for every optimum realizing the connected pattern.The repair edges occupy a constant number of rectangles, so the rectangle net yields the candidate set.Source: §3.9 · p. 17

• Each tag pairs a processed side A with a spanning tree R of G \ A, including direct, virtual, and repaired-tree cases.Virtual and repaired tags add a link between residual components; the virtual link is treated as a zero-capacity edge.Source: §3.10 · pp. 17–18
• A constant-degree expansion of each residual tree preserves the relevant boundaries, which have O(1)-interval representations in the base tree's capacity matrix.The expansion has maximum degree four, and the boundary complexity supports constant-time capacity evaluation.Source: §3.10 · p. 18
• For every tag, the optimizer finds a minimum residual cut crossing at most two edges of R, with shared preprocessing of O(m + n^2) for the base tree.Processing all tags takes O(n|Q_T| log n) time after preprocessing; it avoids rebuilding an Θ(m)-size structure for each tag.Source: §3.10 · pp. 17–18
• The resulting 3-cut candidate has value cG(A) plus the residual minimum-cut value, computed from the capacity matrix without rescanning the edge list for every tag.Only the final returned partition is verified by one O(m) scan.Source: §3.10 · p. 19

3.11 The Cases dA ≥3

• For 3 ≤ dA ≤ 4, a good tree ensures the residual optimum crosses at most one edge of T \ A, so forest completion can enumerate it.If it crosses no edge, the cut is covered by a partition of the forest components; if it crosses one edge, the corresponding edge-removal iteration covers it.Source: §3.11 · p. 19
• Forest completion runs in O(n) time after tree preprocessing and evaluates the target residual cut or its complement.There are at most four components before edge removal and at most five pieces afterward, leaving a constant number of assignments per tree edge.Source: §3.11 · p. 19

3.12 Processing One Candidate Against One Tree

• For a good tree and the true unique medium side A, candidate processing deterministically outputs a 3-cut of value λ.Each produced residual cut costs at most c(EG(B, C)); optimality forces the combined partition to attain λ.Source: §3.12 · p. 20
• Candidate processing uses direct tags for dA = 1 or connected dA = 2, virtual and repair tags for disconnected dA = 2, and forest completion for dA ≥3.The repair case covers the remaining (2, 3, 3) pattern not covered by the virtual tag.Source: §3.12 · p. 20

• If the optimum has two light sides, the crossing candidate or pair scan recovers it; otherwise, tree sampling and candidate processing complete the unique light side.A good sampled tree occurs with high probability, and the algorithm processes both orientations of each candidate cut.Source: §3.13 · p. 21
• The full algorithm runs in O((m + n^2) log^2 n) time, with strict-small handling, sampled trees, retained cuts, and residual-tree processing contributing to the bound.The algorithm uses O(m + n^2) working space by processing sampled trees sequentially.Source: §3.13 · pp. 21–22
• O((m + n^2) log^2 n) time and O(m + n^2) working space yield a minimum 3-cut with probability 1 − n^-Ω(1) for connected multigraphs with positive polynomially bounded integral capacities.Source: §3.13 · p. 22

4.1 Algorithmizing the Light-Cut Bounds

• The light-cut counting arguments of are made algorithmic using non-strict upper bounds, so an overflowing family can yield an explicit k-cut of value at most U.The passage identifies light and medium ranges but does not specify their bounds here.Source: §4.1 · p. 22

4.1.1 Small Cuts

• For a family of distinct U-small cuts, a deterministic certificate either gives a k-cut of value at most U or bounds the family size by 2k.The running time is 2^O(k) e^O(|S|n+m).Source: §4.1.1 · p. 22

4.1.2 Sunflower-Core Search

• For distinct nonempty shores of size at most k, deterministic sunflower search either returns 2k+1 distinct nonempty cores, each supporting a (k+1)-sunflower, or certifies at most D_k n shores.The running time is k^O(k^2) e^O(|X|+N), with D_k = Sun(k,k+1)(2k+1).Source: §4.1.2 · p. 23

4.1.3 Medium Cuts with Small Shores

• For U-medium cuts with shores of size at most k, a deterministic algorithm either finds a k-cut of value at most U or certifies at most D_k n cuts, with D_k ≤ (C′k log k)^k.Its running time is k^O(k^2) e^O(|M|n+m).Source: §4.1.3 · p. 23

4.1.4 Venn Certificates

• For an even k and k/2 U-medium cuts, or the stated atom-count cases for odd k, the generated atoms contain a k-cut of value at most U.For odd k, the cases are at least k atoms from the first (k−1)/2 cuts, or exactly k−1 atoms followed by at least k+1 after the next cut.Source: §4.1.4 · p. 24

4.1.5 Overflow Certificate

• For cuts of value at most 2U/k, OverflowCertificate either finds a k-cut of value at most U or certifies at most C_k n cuts, where C_k ≤ (C′k log k)^k.If the family contains more than C_k n cuts, the certifying overflow rule produces a k-cut of value at most U.Source: §4.1.5 · pp. 25–26

4.2 Sampling a Respecting Tree

• The section gives a deterministic approximate dual tree-packing interface that computes implicit nonnegative tree weights and edge slacks for a connected weighted graph and 0 < η < 1/2.The interface is attributed to.Source: §4.2 · p. 27
• A side of capacity at most 2λ_k(F)/k is (k−1)-respected by a sampled packing tree with probability Ω(1/k).The lemma assumes a connected graph and packing accuracy η≤1/30.Source: §4.2 · p. 28

4.3 A Randomized Reduction to Minimum 3-Cut

• The reduction samples packing-distributed trees, retains light rooted cuts, and recursively completes either side; when too many candidates arise, an overflow certificate yields an optimum.If a sampled tree (j−1)-respects a light side of an optimum, the recursive candidates contain an optimum; a full candidate list instead triggers a certificate cut.Source: §4.3 · pp. 29–30
• With probability 1−n^−Ω(1), the randomized reduction runs in k^O(k^2)n^(k−3)(m+n^2) log^2 n time.Its randomness is confined to the randomized 2- and 3-cut base cases and sampling from tree-packing distributions.Source: §4.3 · p. 30

5.2 Eliminating the Unique Cut Below λ3/2

• When the global minimum cut is below λ3(G)/2, an edge in the intermediate sparsifier can be contracted safely, yielding a quotient whose minimum cut is at least λ3(G)/2.The contraction preserves the fixed optimum 3-cut.Source: §5 · p. 31, §5.2 · pp. 31–32

5.1 Skeleton Construction

• The deterministic skeleton approximates cuts of capacity at most αλ and guarantees every nontrivial cut has scaled capacity at least (1−ξ)λ.It has at most n(log n/ξ)^Oα(1) edges and is constructed in m(log n/ξ)^Oα(1) time.Source: §5.1 · p. 31

5.3 The Deterministic Tree List

• A polylogarithmic-size list of packed trees contains a tree that 2-respects every optimum side of boundary at most 2λ3(G)/3.The construction packs edge-disjoint spanning trees in quotient skeletons and lifts them back to the original graph.Source: §5.3 · p. 32

5.4 The Deterministic 3-Cut Algorithm

• O(m) + Õ(n²) time suffices to find a minimum 3-cut deterministically on weighted multigraphs with positive polynomially bounded integral capacities.The proof shows that the modified algorithm recovers an optimum across its preprocessing and completion cases.Source: §5.4 · pp. 33–34
• The deterministic 3-cut algorithm replaces sampled trees with a deterministic list, processes both sides of candidate cuts, and completes the unique medium side using a good tree.If the earlier cases do not recover the optimum, Lemma 52 supplies a good tree and Lemma 31 recovers the optimum.Source: §5.4 · pp. 33–34

6.1 Deterministic 4-Cut

• O(m) + eO(n^3) time suffices to find a minimum 4-cut deterministically for positive polynomially bounded integral capacities.The algorithm combines a constant-range skeleton with safe contractions: a light optimum side is 3-respected by a packed tree, while safe contractions preserve the optimum and the strict-small cut bound limits branching to three levels.Source: §6 · p. 34, §6.1 · pp. 36–37

6.2 Deterministic Spectral Sparsification

• O(nε^-2) edges suffice for the deterministic (1 ± ε)-spectral sparsifier of, which preserves every cut and j-cut within the same factors.Source: §6.2 · p. 37

6.3 Deterministic Light-Cut Enumeration for k ≥5

• O(m) + k^O(k^2)n^(k−1)log^O(1)n time suffices for deterministic light-cut enumeration when k ≥5.The method uses the full support of a packing in a spectral sparsifier; for any side S with cF(S) ≤2λk(F)/k, some support tree is crossed at most k−2 times.Source: §6.3 · p. 38

6.4 The Derandomized Reduction

• The recursive reduction returns a minimum k-cut deterministically for every fixed k ≥4.For k ≥5, it recursively completes either side of each enumerated cut; when the optimum side is omitted from the list, the overflow rule supplies an optimum candidate.Source: §6.4 · p. 39
• For every fixed k ≥4, the deterministic reduction solves Minimum k-Cut in k^O(k^2)(n^(k−4)m + n^(k−1))log^O(1)n time.It uses the deterministic 4-cut algorithm as its base case and recursively completes either side of each enumerated light cut, with an overflow candidate when the list is full.Source: §6.4 · p. 39
• At most k^{O(k^2)} n^{k-j} parameter-j invocations occur below a top-level parameter k, each retaining O(C_j n) cuts and making O(C_j n) calls with parameter j−1.This count follows because each nonbase invocation makes O(C_j n) recursive calls, all with parameter j−1.Source: §6.4 · p. 39
• Summing over invocations gives k^{O(k^2)} n^{k−1} log^{O(1)} n enumeration work and k^{O(k^2)} n^{k−4}m log^{O(1)} n for graph aggregation and edge scans.There are at most k^{O(k^2)} n^{k−4} parameter-4 leaves.Source: §6.4 · p. 39
• A parameter-j invocation has nonrecursive work O(m_H) + j^{O(j^2)} n^{j−1}.Source: §6.4 · p. 39
• For j ≥ 5, total spectral-sparsifier cost is at most k^{O(k^2)} n^{k−4+ω} log^{O(1)} n, dominated by the n^{k−1} term because ω < 3.Combining the bounds proves the theorem.Source: §6.4 · p. 39

Theorem 48

• For cuts of value at most αλ, J approximates cut capacity within ξλ, while K has n(log n/ξ)^Oα(1) edges and preserves the stated cut bounds.The theorem constructs J and K deterministically in m(log n/ξ)^Oα(1) time, with scales W0,W ≤ λ.Source: A Deferred Proofs for the Skeleton… · p. 41

Cluster decomposition

• The decomposition produces strongly connected clusters for cuts of value at most βλ, with bounded total intercluster boundary and runtime |E(Gj)|(log n/θ)^Oα(1).Padding vertices to a minimum degree supports the strong-cluster construction without changing cuts; deleting the padding preserves cluster strength.Source: A Deferred Proofs for the Skeleton… · p. 42

Small-cluster claim

• The modified small-cluster routine partitions each cluster in |A|^Oα(1) time, using boundary-sparse cuts and cleanup splits to obtain pieces with induced minimum cut greater than ρλ.The cleanup increases total boundary by at most (1 − 2ρ)^−1; first-stage splitting has an Oα(ε^−1 cG(A)) boundary bound.Source: A Deferred Proofs for the Skeleton… · pp. 42–44

Large-cluster claim

• The large-cluster routine partitions a cluster into A0,A1,…,Ar and guarantees the uncrossing bound wG(U \ U*, V(G) \ A) + cG[A](U*) ≤ (1 + ε)cG[A](U).Its proof modifies the isolating-cut construction, rounds capacities, and uses packed forests to obtain the required constant-range coverage and boundary guarantees.Source: A Deferred Proofs for the Skeleton… · pp. 44–45
• The source-family construction covers every U′ with minimum cut at least γλ that is covered by at most Kα internally 0.1λ-connected subsets.Cyclic isolating-cut instances leave at most Kα pieces meeting the active cluster after O(log n) cycles; the additional cycle supports the uncrossing guarantee.Source: A Deferred Proofs for the Skeleton… · pp. 46–48

A Deferred Proofs for the Skeleton Construction

• Uncrossing changes only Oα(1) clusters and groups, with the large-cluster step increasing the cut by O(ε) and the small-cluster step contributing a factor 1/(1 − ε).The two steps together establish both conclusions of the structural cut bound.Source: A Deferred Proofs for the Skeleton… · p. 49
• The hierarchy’s quotient volume halves at each level, and the same hierarchy and degree bound work simultaneously for every target cut.The volume decrease and lower bound on nontrivial quotient volume imply at most L0 levels.Source: A Deferred Proofs for the Skeleton… · p. 50
• Each target cut has an extension in G′ of value at most cF(S) + (θ + θ^3)λ, while every extension of a nontrivial terminal cut has value at least (1 − θ)λ.These bounds support conversion to an unweighted extension graph and splitting off its Steiner vertices.Source: A Deferred Proofs for the Skeleton… · pp. 50–51
• The Nagamochi–Ibaraki certificate preserves target-cut values while bounding cuts, and the proof concludes that all guarantees also hold for the original input graph.The initial truncation preserves every target cut and λ2(F).Source: A Deferred Proofs for the Skeleton… · p. 52

B Consequences for 3-Cut and 4-Cut on Simple Graphs

• The analysis applies the border-and-island framework of with the weighted algorithm on a contracted multigraph.The framework uses p = 2.37134 and a = 3.250386 as rounded upper bounds from.Source: B Consequences for 3-Cut and 4-Cut on… · p. 53
• For k ≥ 4, the small-s branch has exponent f(θ) = 1 + (6k − 6)θ, while the sparsified instance has eO(n/s) vertices and O(sn) edges.The no-island exponent is max{k − 2 − (k − 4)θ, k − 1 − (k − 1)θ}.Source: B Consequences for 3-Cut and 4-Cut on… · p. 53
• For k = 4, the small-s and sparsified branches balance at θ4 = 1/10.At this threshold, f = 1 + 18θ and b1 = 3 − 2θ; for thresholds below 1/2, b0 and b2 are below b1.Source: B Consequences for 3-Cut and 4-Cut on… · p. 53
• O(n^2) time solves Minimum 3-Cut on simple unweighted graphs.The analysis bounds the FPT, two-island, no-island, and one-island branches by O(n^2), up to polylogarithmic factors where stated.Source: B Consequences for 3-Cut and 4-Cut on… · p. 53