Faster exact network checks
Working research note · novelty unconfirmedSuppose a community builds a tightly connected communications mesh. A blocked link changes how the network fits together. An open tool that recomputes exact structural measurements quickly could let people explore many more link-loss and repair scenarios on modest hardware.
This is a possible use of the algorithm developed here. The demonstrated result is mathematical and computational; improvements to an operating communications network have not been established.
21 October 2026 · Petri Mikael Autio, with Codex · Proofs and code generated with AI assistance; independent review pending.
The question behind the shortcut
Graph curvature compares the neighbourhoods at the two ends of a link. Imagine spreading a unit of supplies evenly among each town’s neighbours. How much work does it take to turn one distribution into the other? Easy rearrangement gives positive curvature; sufficiently costly rearrangement gives negative curvature.
Our convention is zero-idleness Ollivier curvature: supplies start on the neighbours, with none held back at the town itself. Changing that convention changes the answer.
The candidate contribution is an exact formula and quadratic all-edge algorithm for a specified graph class. Most links need only a shared-neighbour count; a fully described local exception needs a small exact correction. A broader construction reduces the remaining transport problems to minimum cuts when a related structural parameter is bounded.
Which networks qualify?
Write H for the missing-link graph, the complement of G. The simple fast formula requires that every pair of H vertices has at most two common H neighbours: H contains no non-induced K₂,₃. The algorithm checks this condition first. Its proposed time and memory bounds are O(n²) for all edge values, including recognition and preprocessing, in the indexed representation used in the proof.
For a fixed maximum complement codegree k, the general result is O(poly(k) n²). The deliberately coarse bound O(k¹⁹ n²) is a theoretical guarantee, not a promise that large k is practical. The browser demo implements the codegree-two formula and a general reference fallback.
Try a small network stress test
Change the example or remove and restore a link. The calculation checks the fast rule before using it. Every example is a synthetic, connected, undirected, unweighted graph; this is a structural experiment rather than a prediction of outages or radio performance.
Blue: positiveAmber: zeroRed: negativeDashed: missing
The browser time is one run, not a benchmark. Colour is supplemented by exact values in the table below.
Exact value for every surviving link
| Link | Curvature |
|---|
A small, reproducible timing comparison
These Python timings calculate every surviving edge on seeded synthetic graphs that pass the structural condition. The fast timing includes recognition and preprocessing. Both methods return the same exact rational values.
The baseline is this project’s transparent integer min-cost-flow reference, built for checking the mathematics. It is not an optimised library or a state-of-the-art competitor. This comparison demonstrates the shortcut against that implementation; it does not establish a general practical speed advantage.
| Vertices | Surviving edges | Fast rule, ms | Reference, ms |
|---|---|---|---|
| 8 | 13 | 0.026 | 1.045 |
| 12 | 40 | 0.071 | 19.449 |
| 16 | 80 | 0.080 | 71.101 |
| 24 | 209 | 0.169 | 786.118 |
| 32 | 389 | 0.316 | 3481.285 |
Recorded 21 October 2026 on one Windows machine, Python 3.14.7. Median of 51 fast runs and three reference runs. Graph generation excluded. Small sizes and synthetic inputs limit the conclusion.
What is established here, and what remains open?
The research packet contains written proofs, independent exact transport checks and supporting Lean lemmas. The general implementation agrees with the full reference on 219,371 edge calculations, including every connected labelled graph through six vertices and larger examples. The narrower formula has its own exhaustive replay for eligible graphs.
Across the related research, 35 supporting lemmas compile in Lean 4.19.0. This is partial formalisation. The complete transport identities, reductions and assembly into the final curvature theorems remain in the written arguments.
The accompanying deletion results propose sharp thresholds for the first nonpositive and first strictly negative edge. For ten towns, these are eight and thirteen deletions respectively. They have separate proofs and checks; they are not used as a substitute for validating the algorithm.
Novelty is unresolved. The inspected literature did not reveal an identical exact classification, but that is not proof of priority. Common-mass cancellation, matching theory, integral transport potentials and maximum closure are established methods. The candidate contribution is the specific structural classification and all-edge construction. No independent mathematician has yet reviewed the complete arguments, and no application benefit has been demonstrated.
Prior work and attribution
Jost–Liu supplies the triangle bounds, and Bhattacharya–Mukherjee develops matching-based curvature results. Kelly establishes integral potentials and reduced local linear programmes. These are foundations of the present work.
Chen–Liu–You already studies forbidden subgraphs in graph complements, for Lin–Lu–Yau curvature. Their extremal edge-count paper also supplies the even-order graph used in one of our sharp deletion examples. That graph is credited to them. Our odd-order example uses one fewer deletion, and the proposed universal bounds concern zero-idleness curvature and a different sign condition.
Asai–Yamada motivates the complete-graph deletion question and supplies important deletion families. Nguyen and colleagues uses Ollivier curvature in graph rewiring for learning, illustrating why cheaper exact evaluations could be useful. It does not establish that our specialised algorithm improves those systems.
For the practical claim to become stronger, the next work is clear: independent proof and priority review, comparison with optimised solvers, and tests on real networks that satisfy the structural condition.