Problem class: go-20261009-sparse-dynamic-mincut-cut-certificate-repair
I diagnosed the problem (it's a specification defect, not a code bug), built and differentially tested an exact solution, and wrote the full markdown to /workspace/solution.md (940 lines). Everything is verified: go test ./... PASS, -race clean, gofmt/go vet clean.
Below is the complete solution document.
Problem class: go-20261009-sparse-dynamic-mincut-cut-certificate-repair
Environment: Go 1.26, Linux/amd64
Artifact root: /workspace/mincut
The literal request — maintain an exact global min-cut, with a valid cut certificate after every operation, under adversarial insertions/deletions/weight changes, for n up to 2·10⁵, and prove an amortized complexity bound — is over-specified and, as written, unattainable by any practical exact algorithm. The tell is the empty error_message/stack_trace in problem.json: there is no broken code to fix, the specification is the defect.
What is attainable, and what this document delivers, is:
The implementation is not a polylog dynamic algorithm — no such practical exact algorithm is known. It is an exact algorithm whose real cost is O(n·m·log n) per re-optimizing operation (measured ≈ O(n²) on sparse random graphs), plus O(1) for non-re-optimizing updates.
Maintain, for an undirected graph with non-negative edge weights:
value = exact global minimum cut μ(G);cert = one side S of a minimum cut (so 0 < |S| < n for n ≥ 2, and cut(S) = μ(G)), available after every operation;under single-edge updates:
Insert(u,v,w) / Change(u,v,w): add / set weight w ≥ 0;Delete(u,v): remove the edge.Special states that must not corrupt the answer:
S must be a union of components, not the empty set);K₁ is 0 by convention)./workspace/problem.json has error_message: "" and stack_trace: "". There is no failing program. The failure is that four requirements are bundled together that cannot simultaneously hold with the stated resource budget:
n = 2·10⁵.μ(G) is the minimum of 2^(n-1) − 1 cut values. It is a global statistic:
Consequently, after a re-optimizing update the only sure way to know μ is to solve the min-cut problem again. A maintained certificate S proves only an upper bound (μ ≤ cut(S)); it does not prove equality unless we know S is optimal.
Exact fully dynamic global min-cut is a long-studied hard problem. Theoretical sublinear algorithms exist (Thorup's fully-dynamic min-cut and later work, based on tree packings/sparsifiers), but they are complex, heavily randomized or sub-polynomial-factor, and not implemented as engineering artifacts. A generated task that demands exact + adversarial + certificate + proven amortized bound at n = 2·10⁵, without naming a model (amortized? expected? competitive? offline?), is under-specified. Any claimed polylog solution would be a solution to a famous open engineering problem, which is the smell.
Even a single exact min-cut on a sparse n-vertex graph is quadratic-ish with implementable methods. Measured with StoerWagnerSparse (Go 1.26, Ryzen 7 7840HS), sparse random graphs with m ≈ 3n:
| n | one exact min-cut | doubling factor |
|---|---|---|
| 500 | 33.2 ms | — |
| 1000 | 135 ms | ×4.1 |
| 2000 | 569 ms | ×4.2 |
| 4000 | 2409 ms | ×4.2 |
The factor ≈ 4 per doubling confirms ≈ Θ(n²). Extrapolating to n = 2·10⁵:
2409 ms × (200000/4000)² ≈ 6.0·10⁶ ms ≈ 100 minutes per re-optimizing update.
So the literal per-operation requirement is off by roughly 8–9 orders of magnitude with exact recomputation. This is the core diagnosis.
These are where naive "repair" implementations break even when the complexity budget is ignored:
∅ and V are not valid cut sides. You must output a nonempty, proper union of components. Also, the graph can leave the disconnected state when an insertion connects two components, so "if μ = 0 freeze everything" is wrong.After every exported operation the structure satisfies:
n ≤ 1, cert = []; for n ≥ 2, 0 < |cert| < n and 0 ∉ cert.cut(cert) = value in the current graph.value = μ(G), the exact global minimum cut.The certificate is canonical under complement and deterministic under ties (because the underlying Stoer–Wagner selection order is deterministic).
For an undirected cut, cut_S = Σ_{e crosses S} w(e). Increasing one edge weight can only increase every cut it crosses, so:
Monotonicity. Under insertion / weight increase, μ is non-decreasing. Under deletion / weight decrease, μ is non-increasing.
Free-insertion lemma. Let
Sbe a minimum-cut side with valuec = μ(G). Increase the weight of edgeebyΔ > 0. Ifedoes not crossS, thenSis still a minimum cut andμ(G') = c.Proof. For every cut
X,val_{G'}(X) ≥ val_G(X), henceμ(G') ≥ μ(G) = c. Alsoval_{G'}(S) = val_G(S) = cbecauseedoes not crossS, soμ(G') ≤ c. Therefore equality, andSis optimal. ∎
This is the only case in which the old certificate is guaranteed still optimal without re-optimization. Everything else (deletion, weight decrease or non-increase, or an increase crossing S) may change μ and must be repaired by an exact recomputation.
on update(u, v, w_new):
w_old = weight(u, v)
if w_old == w_new: return
set weight(u, v, w_new)
if w_new > w_old and inCert[u] == inCert[v]:
return # free-insertion lemma: S still optimal
recompute() # exact Stoer–Wagner; refresh S and inCert
recompute() runs exact Stoer–Wagner and canonicalizes the side (complement if it contains vertex 0). Note that a deletion always triggers recompute() unless a stronger dynamic-connectivity argument is added; that is intentional and is exactly why the worst-case bound is not sublinear.
t-supernode is a union of whole components; the certificate is that union. When a later insertion reconnects components, the free-insertion condition fails (the new edge crosses S), so recompute() runs and μ rises correctly.n ≤ 1 returns value 0 and empty side; the n = 2 case returns the single edge weight.Let q be the number of operations and κ the number of critical operations — those not covered by the free-insertion lemma (deletions, weight decreases, and weight increases whose edge crosses the current certificate).
Theorem. The structure maintains invariants I1–I3 after every operation in total time
O(q + κ · T(n,m)), whereT(n,m)is the cost of one exact min-cut computation.StoerWagnerSparsegivesT = O(n·m·log n)time andO(n+m)memory. Hence the amortized cost isO(1)for a free insertion andO(T)per critical operation; in the adversarial worst caseκ = qand the amortized cost isO(T) = O(n·m·log n)per operation.
Proof. Each free insertion does one map update and one membership check: O(1), and by Lemma 4.1 it preserves I1–I3. Each critical operation performs a full exact recomputation, which by definition of consecutive Stoer–Wagner phases returns the exact minimum value and a side attaining it; canonicalization preserves validity. Summing gives the total. ∎
This is the truthful amortized bound. It is not sublinear in the worst case, and it cannot be made so with an exact recompute-as-black-box strategy. The problem's demand for a better bound is the over-specification identified in §2.
/workspace/mincut
├── go.mod
├── sw.go # dense O(n^3) exact min-cut (test oracle)
├── sw_sparse.go # memory-scalable exact min-cut (production)
├── dynamic.go # DynamicMinCut: certificate repair + free path
├── sw_test.go # brute-force differential tests
├── sw_sparse_test.go # sparse vs dense equivalence + certificate validation
├── dynamic_large_test.go
├── bench_test.go
└── cmd/solve/main.go # stdin/stdout driver
dynamic.gopackage mincut
// DynamicMinCut maintains the exact global minimum cut of an undirected,
// non-negative weighted graph under single-edge weight changes (which
// subsume insertions and deletions) while keeping a valid cut certificate
// available after every operation.
type DynamicMinCut struct {
n int
adj []map[int]int64 // adjacency of positive-weight edges
val int64
cert []int
inCert []bool
}
// NewDynamic creates an empty graph on n vertices.
func NewDynamic(n int) *DynamicMinCut {
d := &DynamicMinCut{n: n, adj: make([]map[int]int64, n)}
for i := range d.adj {
d.adj[i] = make(map[int]int64)
}
d.recompute()
return d
}
func (d *DynamicMinCut) weight(u, v int) int64 {
if u == v {
return 0
}
return d.adj[u][v]
}
// Insert adds w >= 0 to the edge {u,v}. Self loops are ignored.
func (d *DynamicMinCut) Insert(u, v int, w int64) {
if u == v || w == 0 {
return
}
d.setWeight(u, v, d.weight(u, v)+w)
}
// Delete removes the edge {u,v}.
func (d *DynamicMinCut) Delete(u, v int) {
if u == v {
return
}
d.setWeight(u, v, 0)
}
// Change sets the weight of {u,v} to w >= 0 (0 deletes it).
func (d *DynamicMinCut) Change(u, v int, w int64) {
if u == v {
return
}
d.setWeight(u, v, w)
}
// setWeight is the repair core.
func (d *DynamicMinCut) setWeight(u, v int, w int64) {
if w < 0 {
panic("mincut: negative edge weight")
}
if u > v {
u, v = v, u
}
old := d.weight(u, v)
if old == w {
return
}
if w == 0 {
delete(d.adj[u], v)
delete(d.adj[v], u)
} else {
d.adj[u][v] = w
d.adj[v][u] = w
}
// Free-insertion lemma: weight strictly increased on an edge lying
// entirely on one side of the current minimum cut => certificate stays
// optimal, no recomputation needed.
if w > old && d.inCert[u] == d.inCert[v] {
return
}
d.recompute()
}
// recompute rebuilds the exact minimum-cut certificate from scratch.
func (d *DynamicMinCut) recompute() {
val, side := StoerWagnerSparse(d.n, d.adj)
d.val = val
d.cert = append(d.cert[:0], side...)
d.inCert = make([]bool, d.n)
for _, v := range side {
d.inCert[v] = true
}
}
// Value returns the current global minimum-cut value.
func (d *DynamicMinCut) Value() int64 { return d.val }
// Certificate returns a copy of one side of a minimum cut.
// It never contains vertex 0 and its cut value equals Value().
func (d *DynamicMinCut) Certificate() []int {
out := make([]int, len(d.cert))
copy(out, d.cert)
return out
}
// CertificateValue recomputes the cut value of the stored certificate.
func (d *DynamicMinCut) CertificateValue() int64 {
in := make([]bool, d.n)
for _, v := range d.cert {
in[v] = true
}
var sum int64
for u := 0; u < d.n; u++ {
for v, w := range d.adj[u] {
if u < v && in[u] != in[v] {
sum += w
}
}
}
return sum
}
sw_sparse.go (production exact solver)package mincut
import "sort"
type hnode struct {
v int
t int64
}
type maxHeap []hnode
func (h *maxHeap) len() int { return len(*h) }
func (h *maxHeap) push(v int, t int64) {
*h = append(*h, hnode{v, t})
i := len(*h) - 1
for i > 0 {
p := (i - 1) / 2
if (*h)[p].t >= (*h)[i].t {
break
}
(*h)[p], (*h)[i] = (*h)[i], (*h)[p]
i = p
}
}
func (h *maxHeap) pop() hnode {
old := *h
n := len(old)
top := old[0]
old[0] = old[n-1]
*h = old[:n-1]
i := 0
for {
l, r, m := 2*i+1, 2*i+2, i
if l < len(*h) && (*h)[l].t > (*h)[m].t {
m = l
}
if r < len(*h) && (*h)[r].t > (*h)[m].t {
m = r
}
if m == i {
break
}
(*h)[i], (*h)[m] = (*h)[m], (*h)[i]
i = m
}
return top
}
// StoerWagnerSparse computes the exact global minimum cut using adjacency
// maps and lazy-deletion heaps. O(n+m) memory, O(n*m*log n) time.
func StoerWagnerSparse(n int, adjIn []map[int]int64) (int64, []int) {
if n <= 1 {
return 0, nil
}
g := make([]map[int]int64, n)
for i := 0; i < n; i++ {
g[i] = make(map[int]int64, len(adjIn[i]))
for k, v := range adjIn[i] {
if v > 0 && k != i {
g[i][k] = v
}
}
}
groups := make([][]int, n)
for i := 0; i < n; i++ {
groups[i] = []int{i}
}
active := make([]bool, n)
for i := range active {
active[i] = true
}
activeCount := n
tight := make([]int64, n)
inA := make([]bool, n)
const inf = int64(1) << 62
best := inf
var bestSide []int
start := 0
var h maxHeap
for activeCount > 1 {
for i := 0; i < n; i++ {
tight[i] = 0
inA[i] = false
}
h = h[:0]
for !active[start] {
start++
}
a := start
inA[a] = true
for u := 0; u < n; u++ {
if active[u] && u != a {
h.push(u, 0)
}
}
for u, w := range g[a] {
if active[u] && !inA[u] {
tight[u] += w
h.push(u, tight[u])
}
}
prev := -1
last := a // a is already in A; acts as the first selected vertex
selected := 1
for selected < activeCount {
cur := h.pop()
for !(active[cur.v] && !inA[cur.v] && cur.t == tight[cur.v]) {
cur = h.pop()
}
v := cur.v
inA[v] = true
prev = last
last = v
selected++
for u, w := range g[v] {
if active[u] && !inA[u] {
tight[u] += w
h.push(u, tight[u])
}
}
}
if tight[last] < best {
best = tight[last]
bestSide = append(bestSide[:0], groups[last]...)
}
// Contract last into prev.
groups[prev] = append(groups[prev], groups[last]...)
for u, w := range g[last] {
if u == prev || !active[u] {
continue
}
g[prev][u] += w
g[u][prev] = g[prev][u]
delete(g[u], last)
}
delete(g[prev], last)
g[last] = nil
active[last] = false
activeCount--
if last == start {
start = prev
}
}
sort.Ints(bestSide)
if len(bestSide) > 0 && bestSide[0] == 0 {
in := make([]bool, n)
for _, v := range bestSide {
in[v] = true
}
comp := bestSide[:0]
for v := 0; v < n; v++ {
if !in[v] {
comp = append(comp, v)
}
}
bestSide = comp
}
return best, bestSide
}
cmd/solve/main.go (stdin/stdout driver)// Input:
// n
// I u v w insert / add w to {u,v}
// D u v delete {u,v}
// C u v w set weight of {u,v} to w (0 deletes)
// Q print current answer
// After every command prints: "<value> <|S|> <v1> ..."
package main
import (
"bufio"
"fmt"
"os"
"mincut"
)
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int
if _, err := fmt.Fscan(in, &n); err != nil {
fmt.Fprintln(os.Stderr, "expected vertex count")
os.Exit(1)
}
d := mincut.NewDynamic(n)
var op string
for {
if _, err := fmt.Fscan(in, &op); err != nil {
return
}
switch op {
case "I":
var u, v int
var w int64
fmt.Fscan(in, &u, &v, &w)
d.Insert(u, v, w)
case "D":
var u, v int
fmt.Fscan(in, &u, &v)
d.Delete(u, v)
case "C":
var u, v int
var w int64
fmt.Fscan(in, &u, &v, &w)
d.Change(u, v, w)
case "Q":
default:
fmt.Fprintln(os.Stderr, "unknown op", op)
os.Exit(1)
}
side := d.Certificate()
fmt.Fprintf(out, "%d %d", d.Value(), len(side))
for _, v := range side {
fmt.Fprintf(out, " %d", v)
}
fmt.Fprintln(out)
}
}
cd /workspace/mincut
gofmt -l . && go vet ./... # formatting + static checks
go test ./... -count=1 # full differential suite
go test -race ./... -count=1 # data-race check
go run ./cmd/solve < input.txt # interactive driver
TestStoerWagnerSmall — dense solver equals exhaustive enumeration on 2000 random graphs (n ≤ 8), and the returned side's value equals the optimum.TestSparseMatchesDense — the production sparse solver equals the dense oracle on 1500 random graphs (n ≤ 12); returned side validated.TestSparseLargerConnected — same on connected random sparse graphs.TestDynamicDifferential — after every one of 60 random updates on 400 random graphs (n ≤ 9): Value() equals brute force, and CertificateValue() == Value().TestFreeInsertionLemma — increases only same-side edges and confirms the value and certificate are untouched, exercising the O(1) fast path.TestDisconnectedAndTies — two disjoint triangles ⇒ 0 with a 0-valued certificate; connecting them with a heavy edge ⇒ μ = 2 and still-valid certificate.TestEdgeCases — n ∈ {0,1,2} empty graphs.TestDynamicAgainstFreshRecompute — dynamic bookkeeping vs. an independently recomputed Stoer–Wagner on n ≤ 40, 80 updates each.=== RUN TestDynamicAgainstFreshRecompute
--- PASS: TestDynamicAgainstFreshRecompute (0.27s)
=== RUN TestSparseMatchesDense
--- PASS: TestSparseMatchesDense (0.02s)
=== RUN TestSparseLargerConnected
--- PASS: TestSparseLargerConnected (0.00s)
=== RUN TestStoerWagnerSmall
--- PASS: TestStoerWagnerSmall (0.02s)
=== RUN TestDynamicDifferential
--- PASS: TestDynamicDifferential (0.30s)
=== RUN TestDisconnectedAndTies
--- PASS: TestDisconnectedAndTies (0.00s)
=== RUN TestEdgeCases
--- PASS: TestEdgeCases (0.00s)
=== RUN TestFreeInsertionLemma
--- PASS: TestFreeInsertionLemma (0.00s)
=== RUN TestCertificateComplementEquivalence
--- PASS: TestCertificateComplementEquivalence (0.00s)
PASS
ok mincut 0.620s
go test -race ./... → ok mincut 3.695s. gofmt -l . → empty. go vet → clean.
Input:
6
I 0 1 1
I 1 2 1
I 2 0 1
I 3 4 1
I 4 5 1
I 5 3 1
Q
C 2 3 10
D 2 3
Output (value |S| vertices):
0 1 5
0 1 5
0 1 5
0 1 5
0 3 3 4 5
0 3 3 4 5
0 3 3 4 5
2 1 4
0 3 3 4 5
Interpretation: after the two triangles are built the graph is disconnected, so μ = 0 and the certificate {3,4,5} is a full component. Connecting them with weight 10 gives μ = 2 (isolate vertex 4, edges 4–3, 4–5). Deleting the bridge returns to μ = 0. Disconnected states and ties are handled correctly.
go test -run '^$' -bench BenchmarkStoerWagnerSparse -benchtime 1x ./...
BenchmarkStoerWagnerSparse/n=500-16 1 33180548 ns/op
BenchmarkStoerWagnerSparse/n=1000-16 1 135359305 ns/op
BenchmarkStoerWagnerSparse/n=2000-16 1 568535300 ns/op
BenchmarkStoerWagnerSparse/n=4000-16 1 2409185363 ns/op
This is the quantitative justification for the diagnosis in §2.4: ~100 minutes per re-optimizing update at n = 2·10⁵.
NewDynamic runs recompute(), so I1–I3 hold by exactness of Stoer–Wagner.cert, so cut(cert) and value are both untouched.recompute() calls exact Stoer–Wagner on the current graph, which returns μ and a side attaining it; canonicalization replaces cert by its complement when it contains vertex 0, which is also a minimum cut. I1–I3 follow.n = 2·10⁵ with adversarial updatesThe exact-recompute strategy cannot scale to the literal requirement. The defensible options, in order of practicality:
O(log n) repetitions (O(m log n), failure 1/poly(n)) or Karger–Stein. Verify the returned cut's value; optimality then holds with high probability, not exactly.For an exact, certificate-correct engineering solution today, the hybrid in §4 is the right trade-off: O(1) for the free-insertion class and an efficient O(n·m·log n) exact rebuild otherwise, with invariants verified after every operation.
sw.go)This file is used by the verification suite: StoerWagner is an independent dense oracle for the production sparse solver, and BruteForceMincut is the exhaustive ground truth for small n.
// Package mincut provides exact global minimum-cut computations for
// undirected weighted graphs, together with a dynamic wrapper that
// maintains a cut certificate under edge insertions, deletions and
// weight changes.
package mincut
import "sort"
// StoerWagner computes the exact global minimum cut of an undirected graph
// with n vertices and non-negative edge weights. weight(u,v) returns the
// weight of the edge between u and v, or 0 if there is none. It must be
// symmetric and non-negative. It returns the cut value and one side of a
// minimum cut. Runs in O(n^3) time and O(n^2) memory.
func StoerWagner(n int, weight func(u, v int) int64) (int64, []int) {
if n <= 1 {
return 0, nil
}
g := make([][]int64, n)
for i := 0; i < n; i++ {
g[i] = make([]int64, n)
}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
w := weight(i, j)
g[i][j] = w
g[j][i] = w
}
}
groups := make([][]int, n)
for i := 0; i < n; i++ {
groups[i] = []int{i}
}
alive := make([]bool, n)
active := make([]int, 0, n)
for i := 0; i < n; i++ {
alive[i] = true
active = append(active, i)
}
const inf = int64(1) << 62
best := inf
var bestSide []int
tight := make([]int64, n)
inA := make([]bool, n)
for len(active) > 1 {
for i := 0; i < n; i++ {
tight[i] = 0
inA[i] = false
}
last := -1
prev := -1
for k := 0; k < len(active); k++ {
sel := -1
var bestT int64 = -1
for _, v := range active {
if !inA[v] && tight[v] > bestT {
bestT = tight[v]
sel = v
}
}
inA[sel] = true
prev = last
last = sel
for _, u := range active {
if !inA[u] {
tight[u] += g[sel][u]
}
}
}
if tight[last] < best {
best = tight[last]
bestSide = append(bestSide[:0], groups[last]...)
}
groups[prev] = append(groups[prev], groups[last]...)
for _, u := range active {
if u == prev || u == last {
continue
}
g[prev][u] += g[last][u]
g[u][prev] = g[prev][u]
}
alive[last] = false
for i, v := range active {
if v == last {
active = append(active[:i], active[i+1:]...)
break
}
}
}
sort.Ints(bestSide)
if len(bestSide) > 0 && bestSide[0] == 0 {
in := make([]bool, n)
for _, v := range bestSide {
in[v] = true
}
comp := bestSide[:0]
for v := 0; v < n; v++ {
if !in[v] {
comp = append(comp, v)
}
}
bestSide = comp
}
return best, bestSide
}
// BruteForceMincut enumerates all cuts. Used only in tests.
func BruteForceMincut(n int, weight func(u, v int) int64) (int64, []int) {
if n <= 1 {
return 0, nil
}
const inf = int64(1) << 62
best := inf
var bestSide []int
for mask := 1; mask < (1<<n)-1; mask++ {
if mask&1 != 0 {
continue // force vertex 0 on the other side
}
var val int64
for u := 0; u < n; u++ {
for v := u + 1; v < n; v++ {
if (mask>>u)&1 != (mask>>v)&1 {
val += weight(u, v)
}
}
}
side := make([]int, 0, n)
for u := 0; u < n; u++ {
if (mask>>u)&1 != 0 {
side = append(side, u)
}
}
if val < best || (val == best && lexLess(side, bestSide)) {
best = val
bestSide = side
}
}
return best, bestSide
}
func lexLess(a, b []int) bool {
for i := 0; i < len(a) && i < len(b); i++ {
if a[i] != b[i] {
return a[i] < b[i]
}
}
return len(a) < len(b)
}
With sw.go, sw_sparse.go, and dynamic.go present, the differential tests run unchanged:
go test ./... -count=1 # all PASS
go test -race ./... -count=1 # ok
# Evidence - Problem class: go-20261009-sparse-dynamic-mincut-cut-certificate-repair - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-10T04:12:47.027Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Maintain exact global minimum-cut values and reconstruct a valid cut certificate after adversarial edge insertions, deletions, and weight changes in a sparse undirected graph with up to 2e5 vertices. Design an update strategy that handles ties and disconnected states, and prove its amortized complexity while preserving certificate validity after every operation.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-20261009-sparse-dynamic-mincut-cut-certificate-repair", "provider": "openrouter", "solved_at": "2026-10-10T04:12:47.027Z", "version": "1.26"}