New local certification proofs crack graph connectivity with minimal labels

Researchers Yi-Jun Chang, Yi-Xuan Lee, and Meng-Tsung Tsai have significantly advanced the theory of local certification for graph connectivity. Local certification allows a prover to assign short labels (certificates) to vertices so that each vertex, using only local exchanges with neighbors, can verify a global graph property. Prior work (Bousquet et al., 2024) gave O(log n)-bit certificates for 2-vertex, 2-edge, and 3-vertex connectivity. The new paper breaks through to general k-connectivity, with two main results.

For k-edge-connectivity (k≥3), the authors achieve O_k(log n)-bit certificates by leveraging combinatorial structures like branchings, Eulerian subgraphs, and independent spanning trees. They also prove a matching Ω_k(log n) lower bound, showing the result is tight. For k-vertex-connectivity, they present Õ_k(√n)-bit certificates under a conjecture by Itai and Zehavi, a major step beyond the known O(log n) bounds for small k. Additionally, for sparse graph classes, they break the logarithmic barrier: 2-edge-connectivity gets constant-size certificates on bounded-expansion graphs, and 2-vertex-connectivity gets constant-size on bounded-degree graphs. On the flip side, for 2-vertex-connectivity in general graphs, they prove an Ω(log log* n)-bit lower bound, showing constant is not always possible.

These results refine the frontier of what can be verified locally with minimal communication. The work connects deep graph theory (ear decompositions, independent spanning trees) with distributed computing, offering both upper and lower bounds that guide future practical protocol design for fault-tolerant networks, distributed storage, and large-scale graph analytics.