[Mac agent] CC engine: fractional-charge / edge-cover node lower bounds #157

Hub: #15. Baseline: main 123011df (CC code identical to e52d15b; CC rules excl,pack,orbf,parity,leaf,overlap, -ub-search Stern). Timing basis: main 12b3e05 tables (optimization/baselines/) and the GH-152 Tier 5 old arm (same CC code as main). PR #155 (-cc-aut=on default) is not merged, so every comparison is against main's CC defaults, and the panels are repeated with -cc-aut=on on both sides. PI approval for this round: 2026-10-29 (Candidate 1 of the CC literature note).

Goal of the round: a stronger node lower bound in the CC engine, so that fewer nodes survive at the hard (refutation) levels of the open TN codes, where the greedy disjoint packing pack is weakest because 4-cycles make odd checks share their candidates.

Background

At a CC node with cluster S, odd-check set U and available qubits A (not in S, not forbidden), every completion e of weight w needs |e \ S| >= tau(U, A), the minimum hitting set of {N(u) & A : u in U}. The chain is degree bound <= nu (integer packing, our pack) <= tau* (LP relaxation) <= tau. Any y >= 0 on U with sum_{u ni j} y_u <= 1 for every j in A is dual feasible, so ceil(sum y) <= tau (weak duality); no LP has to be solved.

Proposals

1. Fractional charge (charge). Local-degree charge y_u = 1/max_{j in N(u) & A} |N(j) & U| (feasible qubit by qubit), then a greedy raise of each y_u by the smallest residual capacity of its qubits (still feasible, never weaker). Bound = max(pack, ceil(sum y)). Exact integer arithmetic (all capacities scaled by lcm(1..max column weight)).
   • Note: "packing plus fractional fill" on top of a maximal greedy packing is always zero (every unpacked odd row meets a packed row, whose qubits have no residual capacity), so the fill is applied to the local-degree start instead.
2. Edge-cover bound (ecover, Gallai). Choose U' within U greedily such that every available qubit touches at most 2 rows of U' (a "2-packing"; it contains the greedy packing). On U' the hitting set is exactly a minimum edge cover of the multigraph whose edges are the qubits touching 2 rows of U' (qubits touching 1 row are loops), so by Gallai's theorem tau(U') = |U'| - nu_match (maximum matching, Edmonds blossom on <= ~40 vertices), provided every row has an available qubit (asserted; otherwise the node is dead). tau(U) >= tau(U'). When every available qubit touches <= 2 odd rows (common at depth >= 2 for column weight 3), U' = U and the bound is the exact tau.
   • This also covers the Okada-Kasai bipartite matching bound a + b - s: for two check classes in which every qubit has at most one neighbour per class, U' = U_a + U_b is such a 2-packing and the matching is bipartite. The per-node Delta <= 2 condition is checked directly, so no structural assertion per code family is needed.
3. Exact tau by LP / Lagrangian* (not selected): equals the dual optimum but costs an LP per node; Lagrangian converges more slowly than proposals 1-2 (literature note, item 8).

Selection

Proposals 1 and 2 as two independent rules in -cc-rules (charge, ecover), both off by default; output with both off is byte-identical to main. They are only evaluated when the packing does not prune and |U| (resp. |U'|) exceeds the remaining budget (otherwise no hitting-set bound can prune), so the per-node cost is paid only where a prune is possible.

Correctness risk: low-medium. Soundness: weak LP duality (charge) and Gallai's theorem (ecover), both applied to the hitting-set relaxation that pack already relies on (every odd row of S needs an odd number >= 1 of qubits of e \ S, all available). The bounds replace the pack test by max(pack, new bound) > remaining budget, so all other rules (excl, orbf, parity, leaf, overlap+forbid, sibling exclusion) keep their arguments unchanged. Integer arithmetic only.

Plan

• Tier 0: byte identity (tier0+1, both engines, -v), make test-cc with new randomized parts (bound vs brute-force tau on random hitting-set instances; ladders vs brute force under all rule subsets), mutants (charge inflated by 1/maxdeg; ecover without the Delta <= 2 check) that must change answers; GF(2) check of every witness.
• -cc-stats: per-level charge/ecover evaluations and prunes, nodes by remaining budget.
• Tiers 1-4: 5-seed medians vs main CC (and vs -cc-aut=on on both sides), node counts per level.
• Tier 5 (6 h, default seed): TN_216/252/288/324 and the other open TN codes, BB_360, BB_756, LP codes. Any new lower bound is reported as PLAUSIBLE; no stems are renamed.
• Server: yfclab2 cores 24-63 only, one process per pinned core, 4 GB cap.

Credits (to go into NOTICE / MODIFICATIONS.md): Banfi, Ferrari, Favano, Tarable, Barletta, arXiv:2610.28008 (charge bound); Okada and Kasai, github.com/kasaikenta/cpm-ldpc-distance (scaled set-cover dual, bipartite matching bound); Gallai's theorem (edge cover = |V| - maximum matching). Clean-room implementation from the published mathematics.