General-graph allocation with independent certificates

Edition: 9 October 2026 Australia/Brisbane. Decision: Prototype certificate integration; defer the literal accelerated backend. No buyer demand or profitable delivery has been established.

Research finding

Family 120 claims one randomized word-RAM program for explicit maximum-cardinality matching in general simple unweighted graphs, with every-path input-size time C p^(1+eta(p)), p=n+m, eta tending to zero, and success probability at least two thirds. It also supplies a witness-preserving prescribed-degree-factor reduction. No family formal-scope document is listed in the baseline.

Problem and buyer

A compatibility planner needs to pair as many participants or resources as possible and explain whether a returned plan is merely feasible or actually maximum cardinality. A randomized solver's attractive headline cannot replace verification of the returned output, model fit and finite operating costs. A useful integration would make those distinctions visible for one repeated planning workload.

What the finding could enable

A practically redesigned construction could permit larger unweighted general-graph matching workloads. The literal accelerated backend currently has astronomical prerequisites, so no such speedup is implemented or claimed. The reviewable capability now is an independent certificate layer around existing solvers: validate candidate edges and, when a supplied odd-component or vertex bound is attained, certify maximum cardinality. This can support a solver comparison, allocation explanation or R&D benchmark integration. The classical certificate is not novel mathematics or the source's accelerated algorithm.

Technical and commercial limits

The source's first accelerated branch uses a=1001. Its backend requires P_star<=b, where Lambda=2^(1000a^2)(1+u), P_star=Lambda^(400a^2), M=2^u, b=M^(1/a^2) and M<=S^2. These imply log2(S)>=200000a^6, already astronomical. This is necessary rather than sufficient. Easy structural completions and the deterministic fallback are separate; the derivation neither disproves the asymptotic result nor rules out a redesigned practical algorithm.

The new audit checks cardinality on the supplied simple graph, not weights, fairness, multiway assignment or constraints omitted by the graph adapter. A feasible matching alone does not prove optimality. A loose upper bound leaves optimality unknown. The separate bounded adapter now proposes a matching and subset using existing NetworkX solves. Only the independent attaining-bound audit grants a certificate. The audit itself does not construct these objects, and neither component implements the source factor reduction. In a real business, model mistakes can dominate solver correctness.

Minimal architecture

Workload and constraint mapping -> existing exact/reference solver -> matching witness plus optional subset certificate -> independent finite audit -> objective/model label -> runtime/memory and disruption report. A future accelerated backend needs its own implementation and crossover benchmark. Preserve the graph, candidate and certificate hashes; do not import a solver's success flag as an optimality proof.

Existing alternatives and differentiation

NetworkX provides blossom-based matching and a maximum-cardinality option, while commercial optimizers handle broader allocation models. A supported adapter should use those methods as baselines. The proposed value is traceable objective/certificate evidence in a recurring decision, or a future measured scaling advantage. A thin wrapper or certificate checker already covered by a buyer's workflow is insufficient differentiation. NetworkX matching API, Gurobi licensing.

Monetization hypothesis

Hypothesis: AUD 5,000–12,000 for a bounded allocation-model and solver-evidence integration. At an assumed AUD 8,000 fee and 30 specialist hours at AUD 180/hour, AUD 2,600 remains before support, sales and overhead; 45 hours exceed the fee. A recurring license needs repeated decisions and a low-maintenance adapter. This overlaps the evidence platform and matching-flexibility dossier 006; do not count the same customer as three independent subscriptions.

Validation experiment

The current certificate utility was checked against independent brute-force optimum matching on all 1,024 five-vertex graphs. It compared all 32,768 subset bounds and found an attaining certificate for every graph. Additional checks reject malformed graphs and invalid candidates, and preserve unknown status for loose bounds. These are finite component checks, not a source-backend speed benchmark. A bounded adapter now passes 72 additional checks and certifies three technical fixtures. The public karate-club graph has 34 vertices, 78 edges and a 13-edge matching certified with a six-vertex subset, using 35 solver calls. A 41-vertex star uses 42 calls, while an 80-vertex generated regular graph attains the vertex bound after one. These one-run local stage timings exclude imports and I/O. The public social graph is a technical fixture, not a customer allocation workload; usefulness and total deployment cost remain untested.

Conditions to reject or defer

Defer the literal source backend until prerequisites are substantially reduced and a fair finite crossover exists. Reject the integration if mandatory constraints are outside unweighted matching, current tools already supply equivalent evidence, or custom adapter/support costs erase the fee. Defer guarantees of weighted quality, fairness or maximum cardinality without an attaining bound or another independent optimality check.

Next concrete action

Use solve_and_audit_matching.py to generate a bounded candidate/subset and independent report. It rejects weights and caps vertices at 256 and calls at 257; the call cap is not a wall-time guarantee. When initial bounds are loose, vertex-deletion solves propose a subset. Incomplete or loose proposals can remain unknown. Next test a realistic public planning-shaped graph and measure the model-adapter effort and usefulness of the explanation. Continue reviewing the source construction separately.

Pinned research sources

• Main matching manuscript: introduction, selected engine parameters, backend guards and uniform program read. The full construction is not independently reproduced.
• Explicit guard calculation and classical certificate argument.
• Saved necessary-parameter bounds.
• Finite certificate validation.

Saved existing-solver integration

Workloads and stage timings, 72 integration checks, public graph fixture. NetworkX 3.4.2 supplied the proposals. The original karate graph's edge weights and club attributes were explicitly omitted to test the unweighted objective. Public graph documentation. No buyer demand, formal program check or new-source speed advantage is established.