arXiv CSopen access

Local Certification of Vertex and Edge Connectivity

Local Certification of Vertex and Edge Connectivity Yi-Jun Chang∗

Yi-Xuan Lee†

Meng-Tsung Tsai‡

Abstract

arXiv:2607.13677v1 [cs.DC] 15 Jul 2026

Local certification is a framework for verifying global graph properties using only local information. In this model, a prover assigns short labels, called certificates, to the vertices of a graph. Each vertex then exchanges certificates with its neighbors and performs a purely local check to determine whether the entire graph satisfies the desired property. This line of research has led to efficient certification schemes for a broad spectrum of graph classes, including minor-closed families, topological graph classes, and graphs defined by forbidden subgraphs. In this paper, we study the local certification of graph connectivity, a classical problem that captures network robustness and is widely studied in distributed computing. Prior work by Bousquet, Feuilloley, and Pierron (JPDC 2024) showed that 2-vertex-connectivity, 2-edgeconnectivity, and 3-vertex-connectivity admit O(log n)-bit certificates, leveraging structural characterizations such as ear decompositions. We go substantially beyond these cases and investigate general k-vertex-connectivity and k-edge-connectivity. We develop new approaches that exploit further connections between connectivity and combinatorial structures, including branchings, Eulerian subgraphs, and independent spanning trees. Our results are as follows. • We obtain a tight Θk (log n) bound for certifying k-edge-connectivity for every k ≥ 3: we give an Ok (log n)-bit certification scheme and prove a matching Ωk (log n) lower bound. Our lower bound applies to both k-edge-connectivity and k-vertex-connectivity. √ • For k-vertex-connectivity, we obtain Õk ( n)-bit certificates for every k under a conjecture of Itai and Zehavi. • We further show that, for k = 2, the logarithmic barrier can be broken on sparse graph classes: 2-edge-connectivity admits constant-size certificates in bounded-expansion graphs, and 2-vertex-connectivity admits constant-size certificates in bounded-degree graphs. In contrast, for 2-vertex-connectivity in general graphs, we prove an Ω(log(log∗ n))-bit lower bound.

∗

National University of Singapore. ORCID: 0000-0002-0109-2432. Email: [email protected] National University of Singapore. ORCID: 0009-0002-9754-9931. Email: [email protected] ‡ Academia Sinica. ORCID: 0000-0002-2243-8666. Email: [email protected] †

1

Introduction

We study local certification of vertex and edge connectivity in distributed networks, modeled as n-vertex simple undirected graphs G. Fix a graph property P to be certified. In a local certification scheme [KKP05], each vertex of G has a distinct O(log n)-bit identifier, and a centralized prover assigns a short label to every vertex. Each vertex then executes a deterministic local verification algorithm, inspecting only its own identifier and label, together with the labels of its neighbors, and outputs either accept or reject. The scheme must satisfy the following completeness and soundness guarantees: Completeness: If G satisfies P, then there exists a labeling under which every vertex accepts. Soundness: If G does not satisfy P, then under every possible labeling, at least one vertex rejects. The efficiency of a scheme is measured by its per-vertex label size, defined as the maximum number of bits assigned to any vertex by the prover. As is the norm in this model, we assume that the underlying network G is connected. For each integer k ≥ 2, we investigate the per-vertex label size required to certify k-edge-connectivity and k-vertex-connectivity. A graph is k-edge-connected if every pair of vertices is connected by at least k edge-disjoint paths. Similarly, a graph is k-vertex-connected if every pair of vertices is connected by at least k internally vertex-disjoint paths. Certifying edge or vertex connectivity is a natural preprocessing step whenever connectivity is used as an algorithmic resource. A local certification scheme can turn this global structural property into a succinct, locally verifiable guarantee, allowing subsequent procedures to safely rely on a prescribed level of connectivity. One example is the work of Bousquet, Feuilloley, and Pierron [BFP24]. They showed that k-vertex-connectivity, for k ≤ 3, can be certified using an O(log n)-bit label per vertex, and further developed local certification schemes for decompositions into 2- or 3-vertex-connected components. The key point is that higher connectivity can dramatically simplify the structure of H-minor-free graphs: for some small excluded minors H, highly connected H-minor-free graphs admit much simpler structural descriptions, which can then be exploited in the design of local certification schemes. Building on this idea, Bousquet, Feuilloley, and Pierron [BFP24] obtain O(log n)-bit certification schemes for several H-minor-free graph classes. This fits into the broader program of locally certifying minor-closed graph classes [CKM25; EL22; FFM+ 20; FFM+ 23], which include fundamental families such as planar graphs and bounded-treewidth graphs. The next challenge is to go beyond 3-vertex-connectivity. Indeed, Bousquet, Feuilloley, and Pierron [BFP24] explicitly asked for efficient local certification schemes for higher vertex connectivity [BFP24, Open Question 58]: Can k-vertex-connectivity be certified with O(log n) bits for any k ≥ 4? Such schemes could open the door to extending this approach to more complicated minorclosed classes and larger excluded minors. At the same time, it is equally important to understand whether logarithmic label size is necessary. In this direction, Bousquet, Feuilloley, and Pierron [BFP24] posed the following question [BFP24, Open Question 57]: Does the certification for k-vertex-connectivity require Ω(log n) bits for any k ≥ 2? Despite graph connectivity being one of the most fundamental graph properties, the complexity of its local certification remains largely open, for both upper and lower bounds. 1

Connectivity is also a key resource in the design of distributed algorithms themselves. For example, Chandra, Chang, Dory, Ghaffari, and Leitersdorf [CCD+ 24] use edge-disjoint spanning trees guaranteed by high edge connectivity to disseminate information efficiently. Their algorithm solves q-message broadcast in a network G of edge connectivity λ in O(((n + q)/λ) log n) rounds. Since the vertices do not know λ in advance, the algorithm uses a guessing procedure to obtain a suitable estimate. A local certificate for k-edge-connectivity suggests another approach: the network can first verify that its edge connectivity is at least k, and then run an algorithm under this certified guarantee. The usefulness of high connectivity extends well beyond information dissemination. High edge connectivity has been exploited in distributed algorithms for fault-tolerant and secure computation [CT18; CPT20; HPY22], and a separate line of work studies algorithms whose guarantees depend explicitly on the vertex connectivity of the underlying graph [CGK14b; CGG+ 17; CGK14a].

1.1

Our results

We begin by showing that, for every k ≥ 3, certifying k-vertex-connectivity or k-edge-connectivity requires per-vertex labels of size Ω((log n)/k) (Theorem 1). This answers [BFP24, Open Question 57] in the affirmative for every constant k ≥ 3. Moreover, for constant k, the lower bound already holds on bounded-degree graphs, that is, graphs whose maximum degree ∆ is bounded by a constant. Interestingly, the situation changes for k = 2. Our lower-bound argument does not extend to this case, and this turns out to reflect a genuine change in complexity: as we show in Proposition 6.1 and Proposition 6.4, on bounded-degree graphs, both 2-edge-connectivity and 2-vertex-connectivity can be certified using only a constant number of bits per vertex. Theorem 1. For every integer k ≥ 3, any local certification scheme for k-edge-connectivity or for k-vertex-connectivity requires per-vertex labels of size Ω((log n)/k), even when each vertex has access to the identifiers of its neighbors. The lower bound holds in bounded-degree graphs when k is a constant. Our second result is a matching upper bound for k-edge-connectivity (Theorem 2). Together with Theorem 1, this gives tight bounds for certifying k-edge-connectivity for every constant k ≥ 3. The certification scheme in Theorem 2 uses a unified construction for all k ≥ 2. The key idea is to move to a directed setting: we replace each edge {u, v} of G with the two antiparallel arcs (u, v) ⃗ and apply Edmonds’ branching theorem [Edm73]. This and (v, u), obtaining a directed graph G, yields a single construction that works for arbitrary k. This contrasts with prior work [BFP24], which uses ear decompositions and their variants to certify 2-edge-connectivity, 2-vertex-connectivity, and 3-vertex-connectivity. While effective for these small values of k, that approach does not appear to extend naturally to arbitrary k. The directed viewpoint is what makes a uniform construction possible. Theorem 2. For every integer k ≥ 2, there is a local certification scheme for k-edge-connectivity with per-vertex label size O(k log n). √ Our third result is an O(k 3 n log2.5 n) upper bound for k-vertex-connectivity (Theorem 3). The result is unconditional for k = 4, and for every k ≥ 5 it holds assuming the Itai–Zehavi conjecture [ZI89]. This conjecture states that an undirected graph G is k-vertex-connected if and only if, for every choice of vertex r ∈ V (G), there exist k independent spanning trees rooted at r. Here, independence means that, for every x ∈ V (G) \ {r}, the r-to-x paths in the k trees are internally vertex-disjoint. 2

The best previous result [BFP24] gives O(log n)-bit local certification schemes for 2- and 3vertex-connectivity, using open ear decompositions and Mondshein sequences, while the case k ≥ 4 was left open as [BFP24, Open Question 58]. We make progress on this open problem by giving the first local certification schemes for k ≥ 4: unconditionally for k = 4, and for all k ≥ 5 under the Itai–Zehavi conjecture. Theorem 3. For every integer k ≥ 4 for which the Itai–Zehavi conjecture holds, k-vertex√ connectivity admits a local certification scheme with per-vertex label size O(k 3 n log2.5 n). In particular, since the conjecture is known to hold for k = 4, 4-vertex-connectivity admits a local √ certification scheme with per-vertex label size O( n log2.5 n). Our lower bound in Theorem 1 applies only for k ≥ 3, leaving open a natural question: what is the complexity of certifying 2-edge-connectivity and 2-vertex-connectivity? In particular, can one beat the logarithmic barrier, or must the label size still grow with n? We show that, on bounded-degree graphs, both properties admit local certification schemes using only a constant number of bits per vertex. For 2-edge-connectivity, we go further and extend the constant-size certification to bounded-expansion graphs, a broad family that includes boundeddegree graphs, planar graphs, and, more generally, every proper minor-closed graph class. Together with Theorem 1, these results reveal a sharp complexity gap between k = 2 and k ≥ 3 on bounded-degree graphs. Theorem 4. For 2-connectivity in restricted graph classes, we obtain the following local certification schemes with constant-size per-vertex labels. All three schemes work even in the anonymous setting where vertices have no identifiers. • There exists a local certification scheme for 2-edge-connectivity with per-vertex label size O(∆ log ∆). • There exists a local certification scheme for 2-vertex-connectivity with per-vertex label size O(2∆ · ∆ log ∆). • Let F be any bounded-expansion graph class. Given the promise that the input graph belongs to F, there exists a local certification scheme for 2-edge-connectivity with O(1) per-vertex label size, where the constant depends on the graph class F . The restriction to sparse graph classes is essential for these constant-size upper bounds. We prove a super-constant lower bound for certifying 2-vertex-connectivity on general graphs in the anonymous setting, via a slight modification of the very recent parity certification lower bound of Bousquet, Feuilloley, Valenzuela, and Zeitoun [BFV+ 26]. The construction inherently exploits the absence of unique identifiers and therefore does not extend to the setting with unique identifiers. Theorem 5. Any local certification scheme for 2-vertex-connectivity requires per-vertex labels of size Ω(log(log∗ n)) when the vertices are anonymous. We summarize the known and new upper and lower bounds on the optimal per-vertex label size for certifying k-edge-connectivity and k-vertex-connectivity in Table 1 and Table 2.

1.2

Technique overview

We present a technical overview of our proofs.

3

Task

Upper and Lower Bounds

Reference

k-edge-connectivity, k ≥ 3

Ωk (log n) Ok (log n)

Theorem 1 Theorem 2

k-vertex-connectivity, k ≥ 3

Ωk (log n)

Theorem 1

3-vertex-connectivity

[BFP24]

4-vertex-connectivity

O(log n) √ Õk ( n)

k-vertex-connectivity, k ≥ 5

√ Õk ( n)

Theorem 3

√ Ω( n)

Proposition 1.1

Theorem 3

(under the Itai–Zehavi conjecture)

Two independent spanning trees

Table 1: Per-vertex label size for k-edge-connectivity and k-vertex-connectivity. Task

Graph Class

Upper and Lower Bounds

Reference

2-edge-connectivity

General Max-degree ∆ Bounded-expansion

O(log n) O∆ (1) O(1)

[BFP24] Proposition 6.1 Proposition 6.10

O(log n) O∆ (1) Ω (log(log∗ n))

[BFP24] Proposition 6.4 Theorem 5

General 2-vertex-connectivity Max-degree ∆ General

Table 2: Per-vertex label size for 2-edge- and 2-vertex-connectivity in the anonymous model. Lower-bound technique for k ≥ 3. Our lower bound follows the cut-and-plug framework of Göös and Suomela [GS16]. The graph-theoretic task is to find, for each property P, a witness graph G ∈ P with a small local interface whose rewiring destroys the property. In our setting, this interface is an edge {u, v} whose endpoints have only O(k) neighbors. Consider two copies G1 and G2 of G, with corresponding edges {u1 , v1 } and {u2 , v2 }. Both G1 and G2 satisfy P, so there are labelings under which all vertices accept. The cut-and-plug operation starts from the vertex-disjoint union G1 ⊎ G2 , deletes the two edges {u1 , v1 } and {u2 , v2 }, and adds the cross edges {u1 , v2 } and {u2 , v1 }. For our witness graphs, this edge-swapped union no longer satisfies P: in fact, its edge connectivity and vertex connectivity are both at most 2. However, if the labels are too short, the two copies can be chosen so that, after this edge swap, every vertex still sees exactly the same local view as it saw in some accepting copy. Hence all vertices still accept the edge-swapped union, contradicting soundness. The rewiring itself uses only two copies, but the proof must first force two copies to be locally indistinguishable to the verifier. To do this, we consider polynomially many copies of the same witness graph, with different assignments of identifiers to the vertices. If the labels have size o(log n), then there are too few possible labeled local views around the small interface to distinguish all these copies. Hence two copies can be chosen so that, after the rewiring, every vertex still sees a local view that it would accept in some valid copy. The verifier is therefore forced to accept the rewired graph, even though it is not k-edge-connected or k-vertex-connected for any k ≥ 3, contradicting soundness. This also explains why the strategy is tight with respect to k = 2: the obstruction produced 4

by the rewiring has connectivity at most 2, which is not enough to refute 2-connectivity. Indeed, on bounded-degree graphs, both 2-edge-connectivity and 2-vertex-connectivity admit O∆ (1)-bit certificates. Upper-bound technique for edge connectivity. For the upper bound on k-edge-connectivity, ⃗ obtained by replacing each edge we move from the undirected graph G to the directed graph G {u, v} with the two antiparallel arcs (u, v) and (v, u). The key observation is that G is k-edge⃗ is k-arc-strongly connected. We can then apply Edmonds’ branching connected if and only if G theorem [Edm73], which witnesses high arc-connectivity through collections of arc-disjoint spanning branchings rooted at a common vertex. The prover certifies these branching structures, and each vertex locally checks their consistency. A key advantage of this approach is that the same construction works for every k: increasing k simply requires certifying more branching structures. Thus, the directed formulation provides a uniform way to certify k-edge-connectivity for arbitrary k. Upper-bound technique for vertex connectivity. For the upper bound for k-vertexconnectivity, we use the Itai–Zehavi characterization in terms of independent spanning trees. Assuming this characterization for the given value of k, it suffices to certify suitable collections of rooted spanning trees such that, for every vertex x, the root-to-x paths in the trees are internally vertex-disjoint. Thus the main building block is to certify that two prescribed spanning trees T1 and T2 , rooted at the same vertex, are independent. A naive certificate would give each vertex its full list of ancestors in both trees, but this can require linear space. We reduce the cost using heavy-light decompositions. In each tree, every root-to-vertex path intersects only O(log n) heavy-light segments, so the prover can encode such a path by a short list of segment-rank pairs. These encodings allow vertices to locally test ancestor relations. The remaining challenge is to ensure that, if independence fails, then some vertex can detect a common internal ancestor on its two root paths. To achieve this, the certificates propagate compact path addresses through the two trees, using a long/short segment threshold to balance the amount of information stored at each vertex: there are few long segments globally, while only few e √n)-bit certificate short-segment vertices appear along any root-to-vertex path. This yields an O( for independence of two rooted spanning trees. We also show that this building block is essentially optimal. Namely, there are n-vertex graphs with two prescribed spanning trees T1 and T2 rooted at the same vertex r such that any local certification scheme for verifying that T1 and T2 are independent requires per-vertex label size √ Ω( n). Proposition 1.1. There are n-vertex graphs G with two spanning trees T1 and T2 rooted at the same vertex r, given as part of the input, such that any local certification scheme for verifying that √ T1 and T2 are independent requires per-vertex label size Ω( n). This independent-tree formulation makes the extension to larger k direct. Once we can certify independence of two rooted spanning trees, we certify pairwise independence among the k trees required for each root. The only additional cost is the number of tree pairs and roots, leading to √ the stated O(k 3 n log2.5 n) per-vertex label size. Constant upper bound for k = 2. Our main building block for certifying 2-edge-connectivity is a decomposition theorem stating that every 2-edge-connected graph can be covered by a constant number of (possibly disconnected) Eulerian subgraphs. This decomposition immediately suggests 5

a certification strategy. Suppose that the prover is allowed to place labels not only on vertices but also on edges, where the label of an edge can be read by both of its endpoints. The prover can then assign a distinct label to each Eulerian subgraph and let every edge inherit the label of the subgraphs containing it. Each vertex then checks that, for every label, the number of incident edges carrying that label is even. On bounded-degree graphs, it is known that labels on edges can be transformed into labels on vertices with only an O∆ (1) overhead [BFV+ 26]. To extend this result to bounded-expansion graphs, the proof first extracts a suitable core structure for 2-edge-connectivity and then transforms the edge-labeling on this core into a vertex-labeling. For 2-vertex-connectivity, we obtain constant-size per-vertex labels on bounded-degree graphs via a reduction to 2-edge-connectivity. We replace each vertex by an edge and partition its neighbors into two nonempty sets, each attached to a different endpoint of the edge. The key property is that the original graph is 2-vertex-connected if and only if every graph obtained in this manner is 2edge-connected. This equivalence is specific to 2-connectivity: the converse direction fails for higher connectivity, and our reduction therefore does not generalize to certifying k-vertex-connectivity on bounded-degree graphs for k ≥ 3.

1.3

Additional related works

Local certification, and more generally distributed interactive proofs, of various graph classes has attracted significant attention in recent years: bounded-pathwidth graphs [BC25], bounded-treewidth graphs [CKM25; FMR+ 24], planar graphs and their variants [FFM+ 20; GP25; GP26; NPY20], bounded-genus graphs [FFM+ 23], cographs [MRR21], distance-hereditary graphs [MRR21], and geometric intersection graphs [JMR22]. Göös and Suomela [GS16] introduced common complexity classes in local certification and prove tight bounds for several graph properties. For example, s–t reachability can be certified in O(1) bits, and to certify that s–t connectivity equal to k, it suffices to use O(log k) bits; the cut-and-plug technique is developed to prove Ω(log n) lower bound for many properties such as parity of the graph size and spanning trees, together with the existing upper bound, the complexity of these problems are Θ(log n). There are also graph properties with certification complexity poly(n), such as symmetricity and non-3-colorability, where the lower bounds are reduced from communication complexity. There is a long line of work that studies the connectivity problem in the CONGEST model. √ Computing the min-cut in a network requires Ω̃( n + D) rounds [DHK+ 11; GK13], where the lower bound also holds for any constant-approximation. In [GK13], they proposed a (2 + ϵ)approximation algorithm that almost matches the lower bound; the approximation ratio was later improved to (1 + ϵ) by [NS14]. For exact min-cut, [GNT20] improved the complexity of [DHN+ 19] √ and provided the first sublinear algorithm; the worst-case optimal round complexity Õ( n + D) was achieved in [DEM+ 21], matching the lower bound. Later on, a universal optimal algorithm for exact min-cut was proposed by [GZ22]. The min-cut problem is also studied in other related models, such as congested clique [GN18] and massively parallel computation [GN20].

1.4

Paper organization

The rest of the paper is organized as follows. In Section 2, we discuss variants of the local certification models and review several standard certification techniques. In Section 3, we present our upper bound for k-edge-connectivity via Edmonds’ branching theorem. In Section 4, we present our upper bound for k-vertex-connectivity via independent spanning trees. We then prove our lower bounds for certifying k-edge-connectivity and k-vertex-connectivity in Section 5. In Section 6, we study

6

2-edge-connectivity and 2-vertex-connectivity. Finally, in Section 7, we conclude with a discussion of future directions.

2

Preliminaries

In this section, we discuss variants of the local certification models and review several standard certification techniques. Notation. Throughout the paper, we use Õ(·), Ω̃(·), and Θ̃(·) to suppress factors of the form log±O(1) n, where n denotes the number of vertices in the original graph G. We also use a subscript k to suppress factors depending only on k, writing Ok (·), Ωk (·), and Θk (·). For example, the bound √ √ O(k 3 n log2.5 n) can be expressed as Õk ( n). For convenience, throughout the paper, the size complexity (or bit complexity) of a local certification scheme refers to the maximum per-vertex (or per-element, defined later) label size.

2.1

Local certification schemes

Our local certification scheme model is precisely the ID-based proof-labeling scheme of Korman, Kutten, and Peleg [KKP05]. In this model, the local verifier at each vertex v has access to ID(v), any prescribed input at v, and the labels assigned by the prover to v and its neighbors. Certification of k-vertex-connectivity or k-edge-connectivity requires no input. In contrast, for tasks such as certifying whether a given edge set forms a spanning tree, the edge set is provided as input by letting each vertex know which of its incident edges belong to the set. We also consider two natural variants of the local certification scheme. In the first variant, the local verifier at each vertex additionally has access to the identifiers of its neighbors. This is exactly the model of locally checkable proofs with local horizon 1 [GS16]. In the second variant, vertices have no identifiers at all; this is known as the anonymous model [KKP05; BFZ25]. These variants are naturally ordered by their computational power. Any upper bound established in the anonymous model immediately carries over to the ID-based setting. Likewise, an upper bound without access to neighbors’ identifiers also applies when such access is available. For lower bounds, the implications are reversed. In the ID-based setting, however, access to neighbors’ identifiers does not affect the asymptotic complexity once the maximum label size is Ω(log n). Indeed, the prover can simply include each vertex’s identifier in its label, and the vertex can locally verify its consistency. In contrast, the anonymous and ID-based settings are fundamentally different. Several tasks, including certifying leader election and spanning trees, are impossible in the anonymous model. On the other hand, in the ID-based setting, every computable function admits a certification scheme by assigning every vertex a description of the entire network. See [KKP05] for further discussion. 2.1.1

Edge certification and degeneracy

In the edge certification scheme [BFP24; FFM+ 23], the setting is the same as in the standard local certification scheme, except that the prover can assign labels to both vertices and edges. The label of an edge can be read by both of its endpoints. The complexity is measured by the maximum per-element label size, which is the maximum of the per-vertex label size and the per-edge label size. To distinguish the two models, we sometimes call the standard local certification schemes, where certificates are assigned only to vertices, the vertex-certification schemes.

7

Edge-certification schemes are a commonly used building block for designing vertex-certification schemes. In the following, we state two well-known transformations from edge-certification schemes to vertex-certification schemes on restricted graph classes. See [BFP24; FFM+ 23] for further applications. For bounded-degree graphs with maximum degree at most ∆, we can transform any edge certification to a vertex certification with only a constant blow-up. The idea is to do a 2-hop coloring on the vertices, and for each vertex, assign a copy of the certificate on each incident edge, along with the color on the other endpoint of that edge. Then each vertex knows which edge each certificate belongs to. See also [BFV+ 26, Proposition 4]. Lemma 2.1. Consider an edge certification of size f (n) for a graph family F. If F has bounded degree ∆, then there exists a (vertex) certification of size O(∆(f (n) + log ∆)). A similar result has been established for sparse graphs with bounded degeneracy. The degeneracy of a graph G is defined to be the minimum number k where G admits an ordering of the vertices such that every vertex has at most k neighbors that are earlier in the ordering. In particular, if a graph is of bounded degeneracy, then the number of edges is linear in the number of vertices. Such an ordering induces an orientation of the edges in which every vertex has bounded out-degree. After certifying this orientation, each vertex is responsible for carrying the certificates of its outgoing edges. In this way, the edge labels can be redistributed uniformly among the vertices. The following lemma formalizes this transformation from edge-certification schemes to vertex-certification schemes on bounded-degeneracy graphs. Lemma 2.2 ([FFM+ 23]). Consider an edge certification scheme of size f (n) for a graph family F. If every graph in F has degeneracy at most d, then there is a (vertex) certification of size O(d(f (n) + log n)).

2.2

Certifying BFS spanning tree

Spanning tree certification is a widely used building block in local certification schemes. In such a scheme, the labels encode the parent–child relationships of a spanning tree and guarantee that either these labels describe a valid spanning tree or at least one vertex outputs reject. Lemma 2.3 ([KKP05]). Let G be a connected graph. Certifying a BFS spanning tree can be done in O(log n) bits. Proof. For completeness, we briefly describe the certification scheme and its verification procedure. • Pick any vertex r ∈ V to be the root. For each vertex v ∈ V , the certificate c(v) contains three fields (r, p(v), dist(v, r)), where r is the root’s ID, p(v) is the parent’s ID, and dist(v, r) is the distance from v to root r. • The verification process contains the following parts: – (All distances are consistent.) Each vertex v checks that the distance from each of its neighbors to the root differs from itself by at most 1. That is, for each u ∈ N (v), dist(u, r) ∈ {dist(v, r) − 1, dist(v, r), dist(v, r) + 1}. – (There exists a root.) Each vertex v with dist(v, r) > 0 checks that its parent is closer to the root. This can be done using p(v) in the certificate of v, and dist(·, v) in the certificates of its neighbors.

8

– (The root is unique.) Each vertex checks that all its neighbors receive the same root ID. For vertex v such that dist(v, r) = 0, v itself is the root. Therefore, we have v check that r = ID(v). Using this scheme, one can certify a spanning forest on a (not necessarily connected) graph G by certifying a spanning tree on each connected component of G.

3

Certifying k-edge-connectivity in Ok (log n) bits

In this section, we prove the following theorem. Theorem 2. For every integer k ≥ 2, there is a local certification scheme for k-edge-connectivity with per-vertex label size O(k log n). For every integer k ≥ 1, we use the equivalence stated in Lemma 3.1 to certify that a simple undirected graph G is k-edge-connected. Lemma 3.1 may be considered as a variant of the strong orientation theorem [Rob39; Nas60]. Lemma 3.1. Let k ≥ 1 be an integer. A simple undirected graph G = (V, E) is k-edge-connected if ⃗ = (V, A) is k-arc-strongly connected, where G ⃗ is obtained from and only if its bidirected version G G by replacing each undirected edge {u, v} ∈ E with the two antiparallel arcs (u, v) and (v, u). Proof. (⇒) Let x, y ∈ V be distinct vertices. Since G is k-edge-connected, there are at least k edge-disjoint undirected paths in G from x to y. These paths witness the existence of at least k ⃗ from x to y because each undirected edge in G corresponds to two arc-disjoint directed paths in G ⃗ antiparallel arcs in G. (⇐) Let x, y ∈ V be distinct vertices. Consider any cut (X, Y ) separating x from y, with x ∈ X ⃗ is k-arc-strongly connected, the directed version of Menger’s theorem [Men27] and y ∈ Y . Since G ⃗ These arcs correspond to distinct edges implies that there are at least k arcs from X to Y in G. of G crossing the cut (X, Y ), because the antiparallel arc of an arc from X to Y is directed from Y to X. Hence every cut (X, Y ) in G has size at least k. By the undirected version of Menger’s theorem [Men27], there are at least k edge-disjoint paths in G from x to y. Another key certificate used by our algorithm comes from Edmonds’ branching theorem (Lemma 3.2). We next explain how to combine Lemma 3.1 with Lemma 3.2 to obtain a local certification scheme for k-edge-connectivity for every integer k ≥ 2. ⃗ is k-arcSuppose that G is k-edge-connected. Then, by Lemma 3.1, its bidirected version G ⃗ ⃗ strongly connected. Fix a vertex r ∈ V (G). By Edmonds’ branching theorem, G contains a collection of k pairwise arc-disjoint out-branchings rooted at r, as well as a collection of k pairwise arc-disjoint in-branchings rooted at r, where an out-branching (resp., an in-branching) rooted at r is a directed spanning tree whose arcs are all oriented away from r (resp., toward r). Thus, the ⃗ and certify their existence to the prover can construct these two collections of branchings in G verifiers. It remains to see why these branchings certify k-edge-connectivity of G. Assume that the ⃗ contains the two collections of branchings described above. We claim verifiers are convinced that G 1 ⃗ If r ∈ that every nontrivial cut (S, V (G) \ S) has at least k arcs entering S in G. / S, then each out-branching contains at least one arc entering S from V (G) \ S. Since the k out-branchings are pairwise arc-disjoint, this gives at least k arcs entering S. If r ∈ S, the same argument applied 1

A cut (S, V (G) \ S) is nontrivial if both S and V (G) \ S are nonempty.

9

to the k in-branchings gives at least k arcs entering S. Hence every nontrivial cut has at least k incoming arcs. ⃗ every nontrivial cut still has at Therefore, after deleting any set of at most k − 1 arcs from G, least one incoming arc. This implies that the remaining digraph is strongly connected, and hence ⃗ is k-arc-strongly connected. By Lemma 3.1, G is k-edge-connected. G ⃗ is not k-arc-strongly Conversely, if G is not k-edge-connected, then Lemma 3.1 implies that G connected. In this case, such two collections of branchings cannot exist; otherwise, the argument ⃗ is k-arc-strongly connected. Hence no prover can certify the existence above would imply that G of these two collections to the verifiers. Lemma 3.2 (Edmonds’ Branching Theorem [Edm73]). Let k ≥ 1 be an integer. Every digraph ⃗ = (V, A) contains k arc-disjoint out-branchings rooted at a vertex r if and only if, for every G nonempty subset S ⊆ V \ {r}, at least k arcs enter S from V \ S. Consequently, it remains for the prover to certify that, for some vertex r ∈ V (G), there exist k pairwise arc-disjoint out-branchings rooted at r. The prover must also provide an analogous certificate for k pairwise arc-disjoint in-branchings rooted at r. In what follows, we focus on the out-branchings case. ⃗ rooted at r, • Prover: Fix a vertex r ∈ V (G) and compute k arc-disjoint out-branchings of G denoted Ti for i ∈ [k]. For each vertex v ∈ V (G) and each i ∈ [k], give the verifier for v a certificate ci (v) := (ID(r), pi (v), depthi (v)) , where pi (v) is the ID of v’s parent in Ti (with pi (r) set to a null pointer) and depthi (v) is the depth of v in Ti . • The verification process contains the following parts: – (The root r is unique.) Each vertex checks that all of its neighbors report the same root identifier ID(r). Since G is connected, if different roots were assigned, then some edge would connect two vertices with different root identifiers, and both of them would reject. The root r also checks that depthi (r) = 0 for all i ∈ [k]. – (Ti consists of n − 1 edges.) Each vertex v with depthi (v) > 0 checks that its parent has a smaller depth. This can be done using pi (v) in the certificate of v, and depthi (pi (v)) in the certificate of its parent pi (v). – (Ti for i ∈ [k] are pairwise arc-disjoint.) Each vertex v ̸= r checks whether the parent identifiers pi (v) over all i ∈ [k] are pairwise distinct. If some arc (x, y) were used in more than one branching, then y would have the same parent x in at least two of the Ti , and this violation would be detected by vertex y. Given the certificates ci (v) for all v ∈ V (G) and i ∈ [k], the verifiers can locally check that, for each i ∈ [k], all vertices agree on the same root and that every vertex other than the root has exactly one parent. Together with the depth consistency checks, it follows that the underlying undirected graph of Ti is connected and has exactly n − 1 edges, and hence is a tree. Since every arc of Ti is oriented from parent to child, so Ti is an out-branching rooted at r. Finally, the verifiers can also check that the Ti are pairwise arc-disjoint. This yields an O(k log n)-bit local certification scheme for k-edge-connectivity for every integer k ≥ 2.

10

4

√ Certifying k-vertex-connectivity in Õk ( n) bits

To explain our upper bound for k-vertex-connectivity, we first recall the following conjecture of Itai and Zehavi [ZI89]: a graph G is k-vertex-connected if and only if for every vertex r ∈ V (G), there exist k independent spanning trees rooted at r. We also recall that independence means that for every vertex x ∈ G \ r, the paths from r to x in the k trees are internally vertex-disjoint. See Figure 1 for an illustration when k = 2. The Itai–Zehavi conjecture is known to hold for every k ∈ {1, 2, 3, 4} [IR88; CM88; ZI89; CLY06]. Using this characterization, we obtain a local certification scheme for k-vertex-connectivity √ with per-vertex label size Õk ( n) for k ∈ {2, 3, 4}. For k ≥ 5, we obtain the same upper bound assuming the Itai–Zehavi conjecture. Theorem 3. For every integer k ≥ 4 for which the Itai–Zehavi conjecture holds, k-vertex√ connectivity admits a local certification scheme with per-vertex label size O(k 3 n log2.5 n). In particular, since the conjecture is known to hold for k = 4, 4-vertex-connectivity admits a local √ certification scheme with per-vertex label size O( n log2.5 n). We note that, by a simple observation, the Itai–Zehavi conjecture implies that a graph G is k-vertex-connected if and only if there exist k distinct vertices r1 , . . . , rk ∈ V (G) (rather than all vertices) such that, for each i ∈ [k], G contains k independent spanning trees rooted at ri . Suppose that G contains such roots but is not k-vertex-connected, then there exists a vertex cut C with |C| < k such that G − C is disconnected. Since C has size less than k, it cannot contain all of r1 , . . . , rk , so some root r∗ remains in G − C. Since G − C is disconnected, there exists a vertex x that belongs to a component of G − C different from the one containing r∗ . This contradicts the existence of k independent spanning trees in G rooted at r∗ , which implies that there are k internally vertex-disjoint paths between r∗ and x, and hence no vertex cut of size less than k can separate them.
Given the above equivalence, certifying 4-vertex-connectivity reduces to certifying that 42 pairs of spanning trees rooted at a common vertex are independent. More generally, assuming the Itai– Zehavi conjecture, the same reduction applies to certifying k-vertex-connectivity for every k ≥ 5. The task of certifying k-vertex connectivity is therefore reduced to the following building block: fix a root r∗ and certify that every pair among the k spanning trees rooted at r∗ is independent. In √ the following lemma, we prove that Õk ( n) bits suffice to certify two independent spanning trees rooted at the same vertex. Lemma 4.1. Given a graph G, a vertex r ∈ G, and two spanning trees T1 and T2 on G rooted at r (the spanning tree inputs are of the form of the certification scheme described in Lemma 2.3), there √ exists an O( n log2.5 n)-bit local certification scheme for certifying that T1 and T2 are independent. Given this lemma, Theorem 3 follows directly. Proof of Theorem 3. Pick arbitrary k vertices r1 , . . . , rk in G. For
each i ∈ [k], we certify k independent spanning trees rooted at ri by applying Lemma 4.1 for k2 pairs of spanning trees rooted at ri . Therefore, the complexity increases by a factor of O(k 3 ). Section 4.1 is devoted to proving Lemma 4.1. In Section 4.2, we show that this approach is essentially tight in the sense that given 2 prescribed spanning trees, certifying that they are √ independent requires per-vertex label size Ω( n).

11

v6

v5

v5

v6

r

r

v4

v2 v3

v5

v5

v6

r

r

v1

v1

v4

v6

v1

v1

v2

v4

v3

(a) Two spanning trees that are vertexindependent.

v4

v2 v3

v2

v3

(b) Two spanning trees that are not vertexindependent

Figure 1: Illustration of independent spanning trees. Both figures demonstrate two spanning trees in a ring rooted at the same vertex r, one in black and the other in dotted lines, oriented from the leaves to the root. In Figure 1a, both spanning trees are paths; the dotted one has v6 as the leaf, and the other has v1 as the leaf. The two trees are vertex-independent. In Figure 1b, the two trees are not vertex-independent (but still edge-independent) since the paths from v4 (and also v5 ) pass through v3 in both trees.

4.1

Proof of Lemma 4.1

We first consider the following naive approach: Given two spanning trees T1 , T2 rooted at r, for a vertex v to verify that the root-to-v path in T1 and the root-to-v path in T2 are internally vertexdisjoint, we provide v with the lists of its ancestors in two trees. Then, if T1 and T2 are not internally vertex-disjoint, then there exists a non-root vertex v, such that the paths from the root to v of both trees go through another non-root vertex u. This means that u is an ancestor of v in both trees, and v could detect u in the lists of its ancestors in both trees. However, this approach would require n log n bits, which is too expensive. We show that the complexity can be reduced to √ Õ( n) via heavy-light decomposition. In Section 4.1.1, we will describe the certificate assignment and its complexity; in Section 4.1.2, we will describe the verification algorithm and the correctness of the entire certification scheme. Then Lemma 4.1 follows. For the rest of the proof, when T is a rooted tree, we denote by T (v) the subtree of T rooted at v. 4.1.1

Certification assignment and the complexity

Heavy-light decomposition and path-encoding Definition 4.2 (Heavy-light decomposition [SE83]). The heavy-light decomposition of a rooted tree T is a partition of its edges into heavy and light edges, such that each non-leaf vertex has one heavy edge to one of its children, which is the child with the largest number of vertices in its subtree. The heavy edges in T induce a set of paths, called segments. Each leaf in T that is not adjacent to any heavy edge is treated as a segment of length 0. This way, each vertex belongs to exactly one segment. Fact 4.3. Consider any vertex in the tree T , the root-to-v path can overlap with at most O(log n) segments. Let T be a tree rooted at r. Denote by Ψ(T ) = {S1 , . . . , St } the set of segments of the heavy-light decomposition on T . 12

r

v v2 v1

v3

Figure 2: An illustration of the heavy-light decomposition. The segments are marked in black. For example, vertex v has two children v1 and v2 , and v1 has more vertices in its subtree, and therefore belongs to the same segment as v. If a leaf does not belong to the same segment as its parent, it is itself considered a segment, see v3 . • For each vertex v ∈ T , define segT (v) = i if v ∈ Si . Recall that each vertex in T belongs to exactly one segment. Moreover, we define the rank of v to be j if v is the j-th closest vertex to the root in SsegT (v) , denoted as rankT (v) = j. We encode the position of v in T by ηT (v) = (segT (v), rankT (v)). • We encode the root-to-v path, denoted by pT (v), as follows: Suppose that the root-to v path in T overlaps with l segments S1′ , . . . , Sl′ . For each j ∈ [l], let uj be the vertex in Sj′ ∩ pT (v) with the largest rank. We define the path-encoding of v, denoted by αT (v), to be a set of segment-rank pairs, which consists of the vertex-encoding of u1 , . . . , ul . More formally, αT (v) = {(segT (uj ), rankT (uj )) : j ∈ [l]}. Observe that the vertex-encoding of v should be the last segment-rank pair contained in αT (v), that is, ηT (v) = (segT (ul ), rankT (ul )). According to Fact 4.3, l ∈ O(log n), and therefore the path-encoding requires O(log2 n) bits. For each vertex v, let AT (v) be the set of the addresses of all ancestors of v in T . AT (v) = {ηT (w) : w ∈ pT (v)}. Note that according to the definition of heavy-light decomposition, all segments must consist of consecutive vertices in an ancestor-descendant relation. Therefore, it holds for every segment that intersects with pT (v), the smallest-rank vertex in the intersection always has rank 1. It follows that AT (v) can be recovered directly from the path-encoding αT (v). Certificate assignment Observe that to certify the independence of T1 and T2 , it suffices for each non-root vertex u to detect whether there exists another non-root vertex v such that u ∈ T1 (v) ∩ T2 (v). For i ∈ {1, 2}, let −i be the complement of i in the set {1, 2}; we say that v is a Ti -ancestor of u if and only if u ∈ Ti (v). For simplicity, let ηi (v) = ηTi (v) and αi (v) = αTi (v). We say that (i, αi (v)) is the Ti -address of v. • For each vertex v, for all i ∈ {1, 2}, include the Ti -address (i, αi (v)) to the certificate of v. • For each vertex v, we choose one of the following certificate assignments. And we will define how to choose between the two options later. – (Option 1.) Include (2, α2 (v)) in the certificates of all the vertices in T1 (v). 13

– (Option 2.) Include (1, α1 (v)) in the certificates of all the vertices in T2 (v). In other words, for each i ∈ {1, 2}, each vertex u receives a list of T−i -addresses of a subset of its Ti -ancestors (including itself). Denote this list by Λi (u). Let the above choice of v be π(v). π(v) = i means that we choose Option i for v. We include this choice in the certificate of v as well. • (Cancellation rules.) For two distinct vertices u, v such that v ∈ T1 (u) and u ∈ T2 (v), we remove some certificates based on the following rules: – If π(u) = π(v) = 1, then for every vertex x ∈ T1 (v), we remove (2, α2 (u)) from Λ1 (x). – If π(u) = π(v) = 2, then for every vertex x ∈ T2 (u), we remove (1, α1 (v)) from Λ2 (x). For each i ∈ {1, 2} and each segment S ∈ Ψ(Ti ), let V (S) be the vertex set of this segment. Then, according to the cancellation rules, we have the following lemma: Lemma 4.4. Given that T1 and T2 are independent. For each i ∈ {1, 2} and each segment S ∈ Ψ(Ti ), for any vertex x ∈ G, there exists at most one non-root vertex v ∈ V (S) such that (i, αi (v)) ∈ Λ−i (x). Proof. We assume that i = 2 without loss of generality. Suppose that for some segment S ∈ Ψ(T2 ), there exist two non-root vertices u, v ∈ V (S) and some vertex x ∈ G such that (2, α2 (u)), (2, α2 (v)) ∈ Λ1 (x). According to the two options of sending information to children, we know that both u and v are ancestors of x in T1 (that is, x ∈ T1 (u)∩T1 (v)) and that π(u) = π(v) = 1. Assume that v ∈ T1 (u) without loss of generality. Since v and u belong to the same segment in T2 , they must be in the ancestor-descendant relationship. Since T1 and T2 are independent and u is a non-root ancestor of v in T1 , it must be the case that u ∈ T2 (v). According to the cancellation rules, we must remove (2, α2 (u)) from Λ1 (x). A contradiction. Given this lemma, we now describe the rules for deciding the choice π(v). • Let τ be a threshold that will be defined later. We say that a segment is long if its length exceeds τ ; otherwise, it is short. For any rooted tree T , let Long(T ) be the set of vertices that belong to some long segments in T , and let Short(T ) be the set of vertices that belong to some short segments in T . • If v ∈ Long(T1 ), then π(v) = 2. Otherwise, π(v) = 1. Complexity Intuitively, when a vertex receives the addresses from a set of vertices, we can bound the number of vertices that come from long segments, since there are not many long segments globally. We can bound the number of vertices that come from short segments, since the total number of vertices in each short segment along the path from any vertex to the root is small. More precisely, the following holds: • If (1, α1 (v)) occurs in the certificates of u, then v ∈ Long(T1 ). According to Lemma 4.4, the number of such v is at most the number of long segments in T1 plus one, which is O( nτ ). • If (2, α2 (v)) occurs in the certificates of v, then π(v) = 1 according to our rule, and one of the following holds: – v ∈ Long(T2 ). In this case, according to Lemma 4.4, the number of such v is at most the number of long segments in T2 plus one, which is O( nτ ). 14

– Observe that if v ∈ Short(T2 ) and π(v) = 1, then v ∈ Short(T1 ) according to our rules. Therefore, v ∈ Short(T1 )∩P1 (r, u). Recall that the number of short segments overlapping with the root-to-u path in T1 is at most O(log n), and the number of such v is at most τ · O(log n). For each vertex v and each i ∈ {1, 2}, the set Λi (v) consists of O( nτ + τ · O(log n)) addresses, each q √ of which need O(log2 n) bits to store. Set τ = logn n , we get an O( n log2.5 n) size bound for our local certification scheme. 4.1.2

Verification algorithm and correctness

Verification algorithm Recall that in our certificate assignment, for each i ∈ {1, 2}, each vertex v receives its own address (i, αi (v)), the choice π(v) of which subtree to send its information to, and a list Λi (v) of the T−i -addresses of a set of its Ti -ancestors. We define |αi (v)| to be the number of segment-rank pairs included in αi (v), and we set (segi (v), ranki (v)) to be the last segment-rank pair in αi (v) The verification algorithm is as follows: • The vertices check the consistency between their path-encoding. More precisely, for each i ∈ {1, 2}, each non-leaf vertex v checks the following: – (Exactly one child that belongs to the same segment.) There exists exactly one child u satisfying |αi (u)| = |αi (v)|. Moreover, αi (u) and αi (v) differ only in the last segmentrank pair, which satisfies segi (u) = segi (v) and ranki (u) = ranki (v) + 1. – (Other children initiate new segments.) For every child w other than u, |αi (w)| = |αi (v)| + 1. Moreover, αi (w) = αi (v) ∪ {(segi (w), ranki (w))}, and ranki (w) = 1. • Each vertex checks that the certificate assignments respect our rules. More specifically, for each i ∈ {1, 2}, each non-leaf vertex v checks the following: – (The two options.) Each vertex checks that either π(v) = 2 and α1 (v) ∈ Λ2 (v), or π(v) = 1 and α2 (v) ∈ Λ1 (v). – (The cancellation rules.) For each child x ∈ Ti (v), the lists of the addresses Λi (v) and Λi (x) satisfy the following: (1.) x’s T−i -address does not appear in Λi (v), that is, α−i (x) ̸∈ Λi (v); and (2.) if there exists u such that α−i (u) ∈ Λi (v) \ Λi (x), then x must be a T−i -ancestor of u and π(x) = i. This can be checked by the path encoding in α−i (u) and the T−i -address of x. If any check fails, vertex v outputs reject. • For each vertex v and each i ∈ {1, 2}, if there exists a label (i, αi (u)) in the certificate for some u ̸= v such that ηi (u) ∈ Ai (v), then output reject. • The vertex outputs accept if all the above verification passes. Correctness Suppose that T1 and T2 are not independent, then there exists vertices u, v such that v ∈ T1 (u) ∩ T2 (u). We assume π(u) = 1 without loss of generality. Let w be the vertex with the largest rank in T1 that satisfies π(w) = 1, u ∈ T2 (w) and v ∈ T1 (w). Such a vertex w exists since we can take w = u. w ̸= v since otherwise v ∈ T1 (u) ∩ T2 (u) and u ∈ T2 (w) will give us a contradiction to the fact that T−i is a tree. 15

We claim that (2, α2 (w)) must be added to the set Λ1 (v). Suppose not, since π(w) = 1, (2, α2 (w)) ∈ Λ1 (w), we can find two vertices y, z along the w–v path in T1 such that y is the parent of z and (2, α2 (w)) ∈ Λ1 (y) \ Λ1 (z). According to our verification algorithm, this means that z must be an T2 -ancestor of w and π(z) = i, otherwise y will output reject. However, z has a larger rank than w in Ti , contradicting the way we chose w. Since v ∈ T1 (u) ∩ T1 (w), v ∈ T2 (u) and u ∈ T2 (w), we have v ∈ T1 (w) ∩ T2 (w). According to our path encoding, w belongs to A2 (v), and v will detect that η2 (w) ∈ A2 (v) with the certificates α2 (w) and α2 (v), which make v output reject according to our verification algorithm.

4.2

Lower bound for certifying two independent spanning trees

√ Since the upper bound for k-vertex-connectivity is Õk ( n), while the lower bound we get in Section 5 is Ωk (log n), a natural question to ask is whether we can do better using the independent tree approach. In this section, we show that certifying the independence of two prescribed spanning √ trees rooted at the same vertex requires Ω( n) bits. More formally, each vertex in the network receives its parents’ IDs in both spanning trees as input, and the task is to verify that the two spanning trees are independent. We construct the lower bound via a standard reduction from the two-party communication complexity of the Set-Disjointness problem. Proposition 1.1. There are n-vertex graphs G with two spanning trees T1 and T2 rooted at the same vertex r, given as part of the input, such that any local certification scheme for verifying that √ T1 and T2 are independent requires per-vertex label size Ω( n). In Section 4.2.1, we will discuss the background about two-party communication complexity, and in Section 4.2.2, we will give the proof of the lower bound. 4.2.1

Two-party communication complexity

The Set-Disjointness problem Let x, y ∈ {0, 1}s be two s-bit strings, each of which can be viewed as an indicator vector of a set. We say that x and y are not disjoint if and only if there exists an index i ∈ [s] such that xi = yi = 1. The truth value of whether x and y are disjoint is denoted as DISJ(x, y). The two-party communication problem of Set-Disjointness (DISJ) is defined as follows. Two players called Alice and Bob, are given inputs x, y ∈ {0, 1}s respectively, and they communicate via a deterministic protocol to decide whether DISJ(x, y) = TRUE or DISJ(x, y) = FALSE. The cost of a given protocol is the worst-case number of bits that the players need to communicate when using this protocol. The communication complexity of DISJ is the minimum cost among all the protocols. Nondeterministic communication complexity In a nondeterministic protocol, each player receives, in addition to its input, an advising string provided by a third party that sees both the inputs of Alice and Bob. We say that the nondeterministic protocol solves some Boolean function f if the following holds: • For each TRUE-instance, there exists an advising string such that the players output accept. • For each FALSE-instance, for any advising string, some player outputs reject. The cost of a nondeterministic protocol is the worst-case length of the advising string. The nondeterministic communication complexity of f is the minimum cost among all the nondeterministic protocols that solve f . 16

For example, the nondeterministic communication complexity of DISJ is O(log s) as we can pick the advising string to be the index i where x[i] = y[i] = 1. Each player can check that the i-th bit of their input is indeed 1. In contrast, it is known that the nondeterministic complexity of DISJ is Ω(s). Fact 4.5 ([KN96]). The nondeterministic communication complexity of DISJ(x, y) is Ω(s). 4.2.2

Lower-bound construction

Let s be an integer. For every instance (x, y) of a Set-Disjointness problem over s2 elements, we define an instance Gx,y on n = (2(s + 1)s + 5) vertices. See Figure 3 for an illustration. • The underlying graph is constructed as follows: – The vertex set V (G) = A ∪ B ∪ P ∪ Q ∪ {v1 , v2 , u1 , u2 , r}, where A = {ai,j : i, j ∈ [s]}, B = {bi,j : i, j ∈ [s]}, P = {pj : j ∈ [s]}, and Q = {qi : i ∈ [s]}. – A forms a grid-like structure where each column is a clique of size s: For each j ∈ [s], let Aj = {ai,j : i ∈ [s]}, then Aj induces a Ks . For each i ∈ [s], {ai,j , ai,j+1 } ∈ E(G) for all j ∈ [s − 1]. – B forms a grid-like structure where each row is a clique of size s: For each i ∈ [s], let Bi = {bi,j : j ∈ [s]}, then Bi induces a Ks . For each j ∈ [s], {bi,j , bi+1,j } ∈ E(G) for all i ∈ [s − 1]. – For each j ∈ [s], the vertex pj is connected to each vertex in Aj ∪ {b1,j } with an edge. For each i ∈ [s], the vertex qi is connected to each vertex in Bi ∪ {ai,s } with an edge. – The vertex v1 is connected to each vertex in P ∪{v2 , r} with an edge, and v2 is connected to each vertex in A ∪ {v1 , r} with an edge. The vertex u1 is connected to each vertex in B ∪ Q ∪ {u2 , r}, and u2 is connected to each vertex in Q ∪ Bs ∪ {u1 , r}. • The two spanning trees on the graph Gx,y are constructed as follows: – For each i ∈ [s], (ai,j , ai,j+1 ) ∈ T1 for all i ∈ [s − 1] and (ai,s , qi ) ∈ T1 . For each j ∈ [s], (pj , v1 ) ∈ T1 . Also, (v1 , r) ∈ T1 and (u1 , r) ∈ T1 . – For each j ∈ [s], (bi,j , bi+1,j ) ∈ T2 for all i ∈ [s − 1] and (pj , b1,j ), (bs,j , u2 ) ∈ T2 . For each i ∈ [s], (qi , u2 ) ∈ T2 . Also, (v2 , r) ∈ T2 and (u2 , r) ∈ T2 . – For each i, j ∈ [s], if xi,j = 0, then (ai,j , v2 ) ∈ T2 . For each j ∈ [s], let A′j = Aj ∩ {ai,j : xi,j = 1}. Let |A′j | = νj , for each t ∈ [νj ], denote by A′ [t] the t-th element in A′j sorted by the i-index. Then (A′j [t], A′j [t − 1]) ∈ T2 for all t ∈ {2, . . . , νj } and (A′j [1], pj ) ∈ T2 . – For each i, j ∈ [s], if yi,j = 0, then (bi,j , u1 ) ∈ T1 . For each i ∈ [s], let Bi′ = Bi ∩ {bi,j : yi,j = 1}. Let |Bi′ | = µi , for each t ∈ [µi ], denote by Bi′ [t] the t-th element in Bi′ sorted by the j-index. Then (qi , Bi′ [1]) ∈ T1 , (Bi′ [t − 1], Bi′ [t]) ∈ T1 for all t ∈ {2, . . . , µi }, and (Bi′ [µi ], u1 ) ∈ T1 . Lemma 4.6. T1 and T2 are independent if and only if DISJ(x, y) = TRUE. Proof. (⇒) If DISJ(x, y) = FALSE, then there exists an index (i, j) such that xi,j = yi,j . According to our construction of Gx,y , there exists a path from ai,j to pj and then to bi,j in T2 ; on the other hand, there is also a path from ai,j to qi to bi,j in T1 . Therefore, the root-to-ai,j path in T1 and T2 intersect at bi,j , which implies that T1 and T2 are not independent. 17

T1

r T2

v1

a1,1

pj

p1

p n

q1

v2

i

b1,1 u1

qi

ai,j

K n+1

u2

bi,j

i

q n

a n, n

j

j

b n, n

n

Figure 3: Lower bound construction for certifying two independent spanning trees. (⇐) We prove that if T1 and T2 are not independent, then DISJ(x, y) = FALSE. If there exists two distinct non-root vertices α and β such that the root-to-α paths in T1 and T2 intersect at β, then β must have one outgoing edge in T1 , one outgoing edge in T2 , and at least one incoming edge in both T1 and T2 according to our construction of Gx,y , which implies that β ∈ A ∪ B. Observe that α should also belong to A ∪ B. (If α ∈ P ∪ Q ∪ {v1 , v2 , u1 , u2 , r}, then the only possible choice of β is r, which is not allowed.) It is not possible that both α, β belong to A: Suppose that α = ai,j , then from the T1 perspective, β must have a same i-index as α; from the T2 perspective, β must have a same j-index as α, this would imply α = β, a contradiction. Similarly, it is impossible that both α, β ∈ B. Therefore, we know that α ∈ A and β ∈ B. Suppose that α = ai,j and β = bi′ ,j ′ , then β is in the root-to-α path in T1 if and only if i′ = i and there exists a path from qi to β in T1 , which implies that yi′ ,j ′ = 1. On the other hand, β is in the root-to-α path in T2 if and only if j ′ = j, and there exists a path from ai,j to pj , which implies that xi,j = 1. In conclusion, we must have xi,j = 1 = yi′ ,j ′ = yi,j since i′ = i and j ′ = j. Proposition 1.1. There are n-vertex graphs G with two spanning trees T1 and T2 rooted at the same vertex r, given as part of the input, such that any local certification scheme for verifying that √ T1 and T2 are independent requires per-vertex label size Ω( n). Proof. Consider any local certification scheme for certifying two independent spanning trees. We construct a nondeterministic protocol for DISJ(x, y) as follows: Alice and Bob are given the input x and y, respectively. They then construct Gx,y based on their inputs. Also, they are both given an advising string that consists of all the certificates along the cut (A ∪ P ∪ {v1 , v2 }, B ∪ Q ∪ {u1 , u2 , r}) in Gx,y . Each player then enumerates all the possible labelings of the vertices that it simulates. If there exists a labeling such that all vertices in its part output accept, then it outputs accept. According to Lemma 4.6, the protocol computes the output TRUE of DISJ correctly – if DISJ(x, y) = TRUE, then there exists an advising string along the cut that both Alice and Bob can fill in their part and accept; on the other hand, if DISJ(x, y) = FALSE, then there is no such 18

advising string. By Fact 4.5, we know that the advising string must have length Ω(s2 ). However, the number of vertices along the cut (A ∪ P ∪ {v1 , v2 }, B ∪ Q ∪ {u1 , u2 , r}) is (4s + 3), therefore, the complexity of any local certification scheme for certifying two independent spanning trees is √ s2 Ω( 4s+3 ) = Ω( n).

5

Lower bounds for k-connectivity for any k ≥ 3

In this section, we prove that for any k ≥ 3, certifying k-vertex-connectivity and k-edge-connectivity both require Ω((log n)/k) bits. Intuitively, we can find a k-(edge or vertex)-connected graph H where there exists a special edge {u, v} whose two endpoints are of bounded degree. We select poly(n) copies of the graph on distinct identifier sets. Suppose that there exists an o(log n) local certification, then there exist two instances H1 and H2 where the local views of the special edges {u1 , v1 } and {u2 , v2 } are the same. Then one can apply the cut-and-plug technique to create a new connected graph with doubled size from H1 and H2 , where edges {u1 , v1 } and {u2 , v2 } are “kicked out” and u1 is reconnected to v2 while u2 is reconnected to v1 . The graph constructed this way always has both vertex and edge connectivity 2. Moreover, the local view of each vertex remains unchanged if one does not consider the IDs of its neighbors; we handle the neighbor IDs as follows. In [GS16], they use a slightly more complicated cut-and-plug technique and prove several Ω(log n) lower bounds even when the neighbors’ IDs are taken into account. In particular, they show that one can “glue” two cycles where all vertices output accept to get one long cycle that does not satisfy the property where all vertices still output accept. We adapt their technique to prove the lower bound for certifying connectivity where the local view of each vertex contains the IDs of its neighbors. The above idea applies to a wider class of properties, which we formalized in the following lemma. See Figure 4 for a visualization. To describe and prove this lemma, we need some more notations. A graph property P is a set of graphs (recall that the property we consider is closed under isomorphism). Let G = (V, E) be a graph, for each vertex v ∈ G, denote by N (v) the neighbors of v in G (not including v). We use ID(v) to represent the identifier of v. Lemma 5.1. Let G ⊆ P be a class of graphs, let β be an integer, and let n0 be a constant. If for each n ≥ n0 , there exists a graph G ∈ G such that G is of size at least n and satisfies the following properties, then it requires Ω((log n)/β) bits to certify P. (i.) There exists an edge {u, v} ∈ E(G) such that |N (u)|, |N (v)| ≤ β, and N (u) ∩ N (v) = ∅. (ii.) For the graph G′ built as follows, G′ ∈ / P: Let G1 and G2 be two disjoint copies of G, and let {u1 , v1 } ∈ E(G1 ) and {u2 , v2 } ∈ E(G2 ) be the edges corresponding to {u, v} in G. Define G′ by starting from the vertex-disjoint union G1 ⊎ G2 and performing an edge swap: delete the edges {u1 , v1 } and {u2 , v2 }, and add the edges {u1 , v2 } and {v1 , u2 }. Proof. Given graph G and edge {u, v} ∈ E(G) that satisfy condition (i.) and (ii.). Since the property P is closed under isomorphism, we assume that the ID(u) = 1, ID(v) = n, the IDs of N (u) belong to {2, . . . , |N (u)| + 1}, and the IDs of N (v) belong to {n − |N (v)|, . . . , n − 1}. Suppose the space of identifiers is I = {1, . . . , n1+c } for some constant c. Let N = nc . Consider any partition of I into size-(n/2) subsets A1 , . . . , AN , B1 , . . . , BN . For each identifier set S defined above, we use S[i] to denote the i-th identifier in S in the natural order. For each pair of (i, j) ∈ [N ]2 , we define a graph C(i, j) that is isomorphic to G (and therefore satisfies property P) on the identifier set Ai ∪ Bj , such that for each t = 1, . . . , n2 , Ai [t] is mapped

19

u

u

N(u)

v

N(v)

v

Bj

Ai N(u)

u

Ai

u

Ai

v′

u′

v′N(v′)

N(u′)

v′

Ai′

N(v′)

N(u′)

u′

v

N(u′)

v

N(v′)

u′

Bj′

Bj′

Ai′

Bj′ N(v)

Bj











u













(b) Four copies of the graph in Figure 4a in different sets of ′ ∪ Bj ′ , Ai ∪ Bj ′ , and Ai′ ∪ Bj . The copies identifiers Ai ∪ Bj , AiN(v′ ) N(v) of the black N(u)vertex and its neighbors are always N(u′on ) the A’s side, and the copies of the white vertex and its neighbors are always Bj Ai′ Ai B’s side. Bj′ on the



(a) A graph with two special vertices (marked black and white)  that are connected with an edge.   Both special vertices have a constant number of neighbors.

N(u)

v′

Ai′

N(v)

Bj

u′

N(u)

Ai

v

u′

N(v)

Bj

Ai′

N(u′)

v′

N(v′)

Bj′

(c) Take the copy with identifier set Ai ∪ Bj and the copy with identifier set Ai′ ∪ Bj ′ . Do a “swap” on the two edges connecting the special vertices in each graph. The local view of every vertex in the resulting graph should be the same as one of the copies in Figure 4b. Therefore, the vertices still output accept, despite the fact that the graph is now 2-connected.

Figure 4: An illustration of the general Ω(log n) lower bound construction.

 



20

to vertex t in G and Bj [t] is mapped to vertex n2 + t in G under the isomorphism. For convenience, we denote ui = Ai [1] and vj = Bj [n]. Let c(i, j) be the ordered label sequence in the view of u and v. c(i, j) = (Ai [|N (u)| + 1], . . . , Ai [1] = ui , vj = Bj [n], . . . , Bj [n − |N (v)|]). Suppose that there exists four distinct indices i, j, i′ , j ′ such that c(i, j) = c(i′ , j ′ ) = c(i, j ′ ) = c(i′ , j), then we construct a graph G′ of size n by gluing the graphs C(i, j) and C(i′ , j ′ ) together: We first remove the edge (ui , vj ) in C(i, j) and the edge (ui′ , vj ′ ) in C(i′ , j ′ ), and then add two edges (ui , vj ′ ) and (ui′ , vj ). We assign the certificates to vertices in G′ as in C(i, j) and C(i′ , j ′ ). One can make the following observations of G′ : • The local view of ui in G′ is the same as its local view in C(i, j ′ ) since c(i, j) = c(i, j ′ ). • The local view of vj in G′ is the same as its local view in C(i′ , j) since c(i, j) = c(i′ , j). • The local view of ui′ in G′ is the same as its local view in C(i′ , j) since c(i′ , j ′ ) = c(i′ , j). • The local view of vj ′ in G′ is the same as its local view in C(i, j ′ ) since c(i′ , j ′ ) = c(i, j ′ ). • For all other vertices in G′ , their local views remain unchanged. Therefore, if there exists a certification scheme where all vertices in C(i, j), C(i, j ′ ), C(i′ , j), and C(i′ , j ′ ) output accept, all the vertices in G′ should output accept under our certification assignment, a contradiction. It remains to show that such indices (i, j, i′ , j ′ ) exist. Consider a complete bipartite graph H = KN,N on vertices A ∪ B. Color the edge (A[i], B[j]) with c(i, j). Suppose that we have a o( logβ n ) certification scheme, the information contains in c(i, j) n is less than λ1 · (|N (u)| + |N (v)| + 2) · logβ n ≤ 4 log for arbitrary constant λ when n sufficiently λ c log n

1

3 large. Pick λ = 12 = N 3 . Therefore, by the c , the number of different colors is less than 2 5 2 pigeonhole theorem, we have a subset of edges E ′ ⊆ E(H) of size at least N 1 = N 3 with the same

N3

color. According to [BS74], a length-4 cycle can be found in E ′ , which is a monochromatic cycle A[i], B[j], A[i′ ], B[j ′ ] in H for some i, j, i′ , j ′ , then c(i, j) = c(i′ , j ′ ) = c(i, j ′ ) = c(i′ , j). Now we apply Lemma 5.1 to prove lower bounds for certifying k-connectivity. Theorem 1. For every integer k ≥ 3, any local certification scheme for k-edge-connectivity or for k-vertex-connectivity requires per-vertex labels of size Ω((log n)/k), even when each vertex has access to the identifiers of its neighbors. The lower bound holds in bounded-degree graphs when k is a constant. Proof. Observe that the graph G′ constructed in Lemma 5.1 has both vertex-connectivity and edgeconnectivity at most 2. Therefore, property (ii) holds, since we assume k ≥ 3. Therefore, our goal is to find the k-edge-connected (or k-vertex-connected) graph class G ⊆ P that satisfies property (i.) in Lemma 5.1. Let n0 be a constant greater than 2k, for any n ≥ n0 , we construct a graph G(n) of size at least n which is k-edge-connected (or k-vertex-connected) as follows: • Pick any k-edge-connected (k-vertex-connected, resp.) graph H(n) of size at least (n − 2). • Add two vertices u, v ̸∈ H(n). Pick two disjoint sets of (k − 1) vertices Su and Sv in H. Connect each vertex in Su to u with an edge, connect each vertex in Sv to v with an edge, and connect u, v with an edge. 21

Note that for k ≥ 3, we can choose H(n) to be a complete graph of size (n − 2). According to our construction of G(n), |N (u)| = |N (v)| = k. Therefore, we get the lower bound by applying Lemma 5.1 to the graph family G = {G(n) : n ≥ 2k}. Remark 5.2. There exist some choices of H(n) such that H(n) is of degree O(k). Therefore, our lower bound works for bounded-degree graphs when k is a constant. For example, one can consider a graph where we partition n vertices into nk parts V1 , . . . , V nk , each consisting of k vertices. For each i ∈ [ nk ], Vi and Vi+1 induce a complete bipartite graph where all edges connect a vertex in Vi and a vertex in Vi+1 .

6

Certifying 2-connectivity in the sublogarithmic regime

In this section, we study the complexity of certifying 2-connectivity in the sublogarithmic region.

6.1

Constant-bit certification schemes for 2-connectivity in restricted graph classes.

In this section, we prove three constant-bit local certification schemes for 2-edge-connectivity or 2-vertex-connectivity stated in Theorem 4. Theorem 4. For 2-connectivity in restricted graph classes, we obtain the following local certification schemes with constant-size per-vertex labels. All three schemes work even in the anonymous setting where vertices have no identifiers. • There exists a local certification scheme for 2-edge-connectivity with per-vertex label size O(∆ log ∆). • There exists a local certification scheme for 2-vertex-connectivity with per-vertex label size O(2∆ · ∆ log ∆). • Let F be any bounded-expansion graph class. Given the promise that the input graph belongs to F, there exists a local certification scheme for 2-edge-connectivity with O(1) per-vertex label size, where the constant depends on the graph class F . We split Theorem 4 into three propositions and prove them separately in the following subsections. In Section 6.1.1 (Proposition 6.1), we give a constant-bit local certification scheme for 2-edgeconnectivity in bounded degree graphs. In Section 6.1.2 (Proposition 6.4), we obtain a constant-bit local certification scheme for 2-vertex-connectivity in bounded degree graphs via a reduction to 2-edge-connectivity. Finally, in Section 6.1.3 (Proposition 6.10), we extend the constant-bit certification scheme for 2-edge-connectivity to bounded-expansion graph classes 6.1.1

2-edge-connectivity in bounded-degree graphs

In this section, we show that 2-edge-connectivity admits a constant-size local certification scheme on bounded degree graphs. Proposition 6.1. There exists a local certification scheme for 2-edge-connectivity on boundeddegree graphs with per-vertex label size O(∆ log ∆), even when the vertices are anonymous.

22

Our upper bound exploits the following lemma on Eulerian subgraph covering. A graph is Eulerian if and only if every vertex has even degree. Given a graph G, we say that an edge e is a bridge of G if removing e increases the number of connected components in G. A graph is bridgeless if it does not contain a bridge. It is known that the edges of a bridgeless graph can be covered by three (possibly disconnected) Eulerian subgraphs. Lemma 6.2 ([AT85]). An undirected graph G is 2-edge-connected if and only if its edge set E(G) can be covered by three (possibly disconnected) Eulerian subgraphs (V (G), Ci ) for i ∈ [3]; that is, C1 ∪ C2 ∪ C3 = E(G). Our first observation is that 2-edge-connectivity admits a constant-bit edge-certification scheme via a simple application of Lemma 6.2. Lemma 6.3. There exists an O(1)-bit edge-certification scheme for 2-edge connectivity. Proof. For each i ∈ [3], color all the edges in Ci with color i. Each vertex then checks that (1.) for each color i ∈ [3], the number of incident edges that are colored i is even, and (2.) every edge is colored by at least a color in [3]. Proposition 6.1 then follows immediately by a transformation from edge-certification to vertexcertification. Proof of Proposition 6.1. According to Lemma 2.1, we can transform this O(1)-bit edgecertification scheme to an O(∆ log ∆)-bit vertex certification scheme for graphs with max-degree ∆. 6.1.2

2-vertex-connectivity in bounded degree graphs

In this section, we show that 2-vertex-connectivity can be certified with O(1) bits on bounded degree graphs via a reduction to 2-edge-connectivity. Proposition 6.4. There exists a local certification scheme for 2-vertex-connectivity on boundeddegree graphs with per-vertex label size O(2∆ · ∆ log ∆), even when the vertices are anonymous. The intuition is to transform the graph G into a set of graphs by making the vertices of G into edges and reconnecting with its neighborhood in a way such that G is 2-vertex-connected if and only if all the transformed graphs are 2-edge-connected. Transforming a 2-vertex-connected graph into a 2-edge-connected graph Given a 2vertex-connected graph G = (V, E), we construct a graph G′ = (V ′ , E ′ ) by the following operation: • For each vertex v ∈ G, make it into a super vertex ψ(v) = {v0 , v1 }. Add the vertices v0 , v1 to V ′ , and add an edge {v0 , v1 } to E ′ . • For each vertex v ∈ G, partition N (v), the neighborhood of v, into two non-empty subsets N0 (v), N1 (v). • For each pair of vertices {u, v} ∈ E and i, j ∈ {0, 1}, add an edge {ui , vj } to E ′ if and only if v ∈ Ni (u) and u ∈ Nj (v). According to the rules of how we construct G′ , we have the following observation:

23

Observation 6.5. For each pair of vertices u, v ∈ G, {u, v} ∈ E if and only if there exists some edge {ui , vj } ∈ E ′ between ψ(u) and ψ(v). We claim that if the original graph G is 2-vertex-connected, then the resulting graph G′ is 2-edge-connected. Claim 6.6. If G is 2-vertex-connected, then G′ is 2-edge-connected. Proof. Suppose that G′ is not 2-edge-connected, then there exists a bridge e = {x, y} ∈ E ′ that splits the graph into two connected components X and Y where x ∈ X, y ∈ Y . Suppose that x ∈ ψ(u) and y ∈ ψ(v) for some u, v ∈ V , then for each w ∈ V , w ̸∈ {u, v} the two vertices in ψ(w) ⊆ V ′ must belong to the same side of the cut (X, Y ). Let S = {s ∈ V : ψ(s) ⊆ X} and T = {t ∈ V : ψ(t) ⊆ Y }. If u ̸= v, then according to Observation 6.5, there is no edge between S ∪ {u} and T ∪ {v} except for {u, v}. Then removing either u or v will disconnect the graph. Otherwise, u = v and x = u0 , y = u1 , then there is no edge between S and T . Note that in this case, S and T will be non-empty since we have partitioned N (u) into two non-empty sets. Thus, removing u will disconnect the graph. In both cases, we arrive at a contradiction to the fact that G is 2-vertex-connected. Claim 6.7. If G has a vertex cut {v}, then there exists a partition of N (v) such that {v0 , v1 } is a bridge in G′ , no matter how we partition the neighborhoods of other vertices. Proof. Let S, T ⊆ V be two vertex sets that are disconnected after removing v from G. Let N0 (v) = N (v) ∩ S and N1 (v) = N (v) ∩ T . Then {v0 , v1 } is a bridge in G′ . Proof of Proposition 6.4. Let G = (V, E) be a graph of maximum degree ∆. Then for each v ∈ V , there exist at most 2deg(v)−1 − 1 ≤ 2∆−1 − 1 ways of partitioning N (v). Let t(v) = 2deg(v)−1 − 1, and t = 2∆−1 − 1. Let the set of partitions be Γ(v) = {Γi (v)}ti=1 , where Γi = {N0i (v), N1i (v)}, Γi (v) ̸= Γj (v) for every 1 ≤ i < j ≤ t(v) and Γi (v) = Γt(v) (v) for all t(v) ≤ i ≤ t. For each i ∈ [t], we construct a graph Gi using the partition Γi (v) for every vertex v ∈ G. According to Claims 6.6 and 6.7, if G is 2-vertex-connected, all {Gi }ti=1 are 2-edge-connected. Otherwise, there exists some Gi∗ , i∗ ∈ [t] such that Gi∗ has a bridge. Therefore, it suffices to simulate the certification of 2-edge-connectivity simultaneously for each Gi . Our certification scheme is as follows: • For each v ∈ V , assign the list of partitions Γ(v) = {Γi (v)}ti=1 to v. Each of the partitions can be stored in O(1) bits by first doing a 2-hop coloring on V , and then encoding the partition of N (v) by a partition of the colors in N (v). • For each i ∈ [t], let ci be the certificate assignment for 2-edge-connectivity when the underlying graph is Gi . For each v ∈ V , assign v the list of certificates {(ci (v0 ), ci (v1 ))}ti=1 . • Each vertex v ∈ V runs the following verification algorithm: – First check that the 2-hop coloring (for encoding the partition) is proper, this can be done by having each vertex check that no color appears twice in their neighborhood. Then check that the set of partitions Γ(v) indeed contains all possible partitions of its neighborhood, which can be done with the knowledge of its neighborhood in the original graph.

24

– For each i ∈ [t], each vertex v ∈ V has the knowledge of the local graph topology of Gi by looking at the partition of its neighbors and itself. Therefore, it can simulate the verification algorithm of v0 and v1 on Gi with the certificates {(ci (v0 ), ci (v1 ))}. If the verification fails for some i, it outputs reject. Otherwise, it outputs accept. The correctness of this certification scheme follows from the correctness of certifying 2-edgeconnectivity on bounded-degree graphs. The size of the certificates blows up by a factor of O(t) = O(2∆ ), which gives us the size bound of certificates. 6.1.3

2-edge-connectivity for bounded-expansion graph classes

In this section, we show that the constant-bit certification for 2-edge-connectivity in bounded degree graphs (Proposition 6.1) can be further generalized to bounded-expansion graphs, which include several well-known graph classes such as bounded-degree graphs and minor-closed graph classes. The formal definition is stated below. Definition 6.8 (t-shallow minor). Let G and G′ be two graphs. We say that G′ is a t-shallow minor of G if there exists a subgraph H of G and a partition of the vertices of H into connected sets with radius (measured in H) at most t, such that G′ is obtained from H by contracting these connected sets. Definition 6.9 (bounded expansion). A class of graphs F is said to have bounded expansion if there exists a function f such that for each graph G ∈ F , each t ≥ 1, every t-shallow minor G′ of |E(G′ )| G satisfies that |V (G′ )| ≤ f (t). Proposition 6.10. Let F be a bounded-expansion graph class. Given the promise that the input graph belongs to F, there exists a local certification scheme for 2-edge-connectivity with O(1) pervertex label size, where the constant only depends on the graph class F. Before proving Proposition 6.10, we first provide some intuition and review the necessary graphtheoretic background. Our approach again builds on the edge certification scheme in Lemma 6.3. The main obstacle was that when the degree is unbounded, transforming edge-certification schemes to vertexcertification schemes requires vertices to know which edges it is simulating, which is precisely what gives rise to the additive Θ(log n) term in Lemma 2.2. We show that for bounded expansion graphs, this obstacle can be overcome via an application of a very recent certification scheme for pseudoforest [BFV+ 26]. A pseudoforest is a graph where each connected component has at most one cycle. It is easy to see that every pseudoforest admits an edge-orientation with maximum out-degree at most 1. Given such an orientation, we say that a vertex u is the parent of vertex v if and only if v is oriented into u; otherwise, u is a child of v. Given a labeled graph G, we say that the labeling encodes a pseudoforest in G if for every vertex in G, by investigating the labels of its neighborhood, the vertex knows which neighbor is its parent and which neighbors are its children in that pseudoforest. In [BFV+ 26], they show that for bounded expansion graphs, there exists an O(1)-bit encoding for a BFS spanning forest. Moreover, their encoding scheme guarantees that even if the prover lies, the certificates still at least encode a pseudoforest. Lemma 6.11 ([BFV+ 26]). Let F be a bounded-expansion graph class. There exists an O(1)-bit local certification scheme that satisfies the following properties:

25

• (Completeness.) If the prover is honest, the certificate assignment encodes a BFS spanning forest. • (Soundness.) If the verifier accepts on every vertex, then the certificate assignment encodes a pseudoforest. We then observe that, as long as a partition of edges into a constant number of pseudoforests is given as input to the vertices, transforming edge-certification to vertex-certification incurs only a constant overhead by letting the children take the responsibility of simulating the edge connected to the parent. More formally, a d-pseudoforest decomposition of a graph is a partition of its edges into d subsets, each inducing a pseudoforest. Similarly, we say that a d-pseudoforest decomposition is encoded in a labeled graph if for each i ∈ [d], each vertex can determine, by inspecting the labels in its neighborhood, which of its neighbors are its parent and children in the i-th pseudoforest. In the following lemma, we show that if a d-pseudoforest decomposition is encoded in the input graph, then we can transform an edge-certification scheme into a vertex-certification scheme with only a factor of d overhead. Lemma 6.12. Consider a graph family F and an edge-certification for F of size f (n). If a dpseudoforest decomposition is encoded for every graph in F , then there exists a (vertex) certification of size d · f (n). Proof. Let G = (V, E) be a graph in F. For each edge e ∈ E, denote by c(e) the certificate assignment on e. Denote by Ti the i-th pseudoforest in the decomposition. We now construct a vertex-certification scheme as follows: • (Prover.) For each edge e = {u, v} ∈ Ti , suppose that v is the parent of u in Ti , remove the certificate c(e) from e and assign (i, c(e)) to the vertex u. • (Verifier.) For each vertex v ∈ V , recover the edge certification for each incident edge by investigating the certificates of its neighbors, and then run the verification scheme as in the original edge certification scheme. Since each vertex has at most 1 parent in each pseudoforest, it receives at most d certificates from its incident edges, and therefore the total certificate size is at most d · f (n). Combining with the edge-certification scheme for 2-edge-connectivity in Lemma 6.3, we derive the following lemma. Lemma 6.13. Let F be a labeled graph family such that a d-pseudoforest decomposition is encoded for every graph in F . Then there exists an O(1)-bit local certification scheme for 2-edge-connectivity on F. Proof. First, apply Lemma 6.3 to obtain an O(1)-bit edge-certification scheme and then transform it into a vertex-certification scheme using Lemma 6.12 with a constant overhead. Our main idea is to use the pseudoforest certification scheme of Lemma 6.11 to simultaneously encode a sparse subgraph that preserves 2-edge-connectivity and a pseudoforest decomposition of this subgraph. We then apply the edge-certification scheme of Lemma 6.3 to this subgraph and use the pseudoforest decomposition to redistribute the edge labels to the vertices, thereby obtaining a constant-bit vertex-certification scheme. To extract this sparse core via Lemma 6.11, we will invoke the following graph-theoretic tools. Let G = (V, E) be a graph, a certificate for k-edge-connectivity (k-vertex-connectivity, resp.) of 26

G is a subset of edges E ′ ⊆ E such that the subgraph G′ = (V, E ′ ) is k-edge-connected (k-vertexconnectivity, resp.) if and only if G is k-edge-connected (k-vertex-connectivity, resp.). It has been shown that for both k-edge-connectivity and k-vertex-connectivity, there exists a certificate of degeneracy at most k [NI92; CT91] by finding BFS (breadth-first search) spanning forest iteratively. Lemma 6.14 ([NI92; CT91]). Let G = (V, E) be a graph, and for i = 1, . . . , k, let Fi be the edge set k of a BFS spanning forest of G \ (∪i−1 j=1 Fj ). Then ∪i=1 Fi is a certificate for both k-edge-connectivity and k-vertex-connectivity. Intuitively, letting k = 2, we can use Lemma 6.11 to encode the sparse certificate in Lemma 6.14 by encoding the BFS spanning forest iteratively. However, since provers may cheat, in which case we only get pseudoforests that do not span the entire graph, we need to extract another subset of edges to ensure that the bridge is preserved. Lemma 6.15 ([Jae79]). For any graph G and any spanning tree T of G, there exists a forest F ⊆ T such that the graph G′ = G \ F obtained by removing every edge in F from G is an Eulerian subgraph of G. Observe that every graph with a bridge is not an Eulerian graph, as there are at least two vertices with odd degree. Consequently, a subgraph that preserves bridges can be verified by a degree-parity check. Claim 6.16. Given a graph G = (V, E) that contains a bridge. For any edge set E ′ ⊆ E satisfying that for each vertex v ∈ V , degE ′ (v) ≡ degG (v) mod 2, E ′ contains every bridge in G. Proof. Let G′ be the subgraph of G induced by the edge set E − E ′ . Observe that for each vertex v ∈ V , degG′ (v) ≡ (degG (v) − degE ′ (v)) ≡ 0 mod 2. Therefore, G′ is an Eulerian subgraph of G, and thus does not contain any bridge of G. Now we are ready to prove Proposition 6.10. Proof of Proposition 6.10. Certificate assignments. Prover assigns the following certificates to the vertices: 1. Specify two BFS spanning trees using Lemma 6.11, with distinct sets of labels. Denoted as T and T1 . 1-1. Specify a forest F ⊆ T whose removal makes the graph Eulerian. The existence of F is guaranteed by Lemma 6.15. To encode F , the prover does the following: For each edge e ∈ F , suppose that e = (u, v) is oriented from u to v, then the prover puts a special symbol ∗ on u. 1-2. Specify a BFS spanning forest T2 on the graph G − T1 using Lemma 6.11 with a distinct set of labels from T1 . Note that T and T1 can be arbitrary BFS spanning trees; they can also be identical. We distinguish them here only for the ease of presentation. 2. Certify 2-edge-connectivity on the subgraph G′ induced by the edge set F ∪T1 ∪T2 . Since we have certified three pseudoforests in step 1., we can apply the O(1)-bit certification scheme in Lemma 6.13. Verification algorithm. The verifier recovers the edge set encoded in item 1-1 by investigating the certificates assigned in its neighborhood. This edge set is denoted as F ′ to distinguish between the set F guaranteed in Lemma 6.15. 27

• (Degree parity check.) Each vertex v checks that degF ′ (v) ≡ degG (v) mod 2. • Each vertex runs the verification algorithm of 2 on the subgraph induced by the edge set F ′ ∪ T1 ∪ T2 . Let us now prove the correctness of the algorithm. For completeness, we note that according to Lemma 6.14, the subgraph of G induced by the edge set T1 ∪ T2 is a certificate for 2-edgeconnectivity. G[F ∪ T1 ∪ T2 ] is a subgraph of G that contains G[T1 ∪ T2 ], and therefore also a certificate for 2-edge-connectivity of G. Since prover has encoded three pseudoforests F , T1 , and T2 , the completeness follows from applying Lemma 6.13 to G[F ∪ T1 ∪ T2 ]. For soundness, according to Claim 6.16, if the degree parity check passes on every vertex, then F ′ should contain all the bridges in G. Moreover, since prover has encoded three pseudoforests F ′ , T1 , and T2 , applying the soundness of the certification scheme in Lemma 6.13 to G[F ′ ∪ T1 ∪ T2 ], the verifier will reject when F ′ contains a bridge. Remark 6.17. The constant in Proposition 6.10 comes from the use of conflict-free colorings [BFV+ 26]. Since a 2-hop coloring is a conflict-free coloring on bounded-degree graphs, Proposition 6.1 is subsumed by Proposition 6.10.

6.2

An ω(1) lower bound for 2-vertex-connectivity in the anonymous model

In contrast to the constant-size certification scheme for bounded-degree graphs in Proposition 6.4, we give an O(log(log∗ n))-bit lower bound for certifying 2-vertex-connectivity in the anonymous model. The lower bound construction is a slight modification of the parity lower bound in [BFV+ 26] with the observation that their accepting instance can be made 2-vertex-connected. See Figure 5 for an illustration. Theorem 5. Any local certification scheme for 2-vertex-connectivity requires per-vertex labels of size Ω(log(log∗ n)) when the vertices are anonymous. To prove Theorem 5, we use the same approach as in [BFV+ 26]. The following lemma is an implication of the Finite Union Theorem (see [BFV+ 26, Theorem 12, Theorem 13] and the reference therein) and Lemma 15 in [BFV+ 26]. Lemma 6.18 ( [GRS91; Set98; BFV+ 26]). For every integer m, let c = f (m) be the minimum number of colors for which there exists a coloring of all non-empty subsets with c colors such that no two disjoint subsets ∅ ⊊ S1 , S2 ⊆ [m] satisfy that S1 , S2 , and S1 ∪ S2 all receive the same color. Then c ∈ Ω(log∗ m). Proof of Theorem 5. We first construct a graph H = (V, E) as follows: • First, we have a ground set M = [m]. Let B = M ∪ {i + m : i ∈ M } = {1, . . . , m, m + 1, . . . , 2m} ⊆ V . The set B induces a clique K2m in G. That is, every vertex in B is connected to all other vertices in B. • For each S ⊆ M , let S∥m = {s + m : s ∈ S} we introduce a new vertex vS ∈ V that connects to all vertices in S ∪ S∥m . Note that for every S, (S ∪ S∥m ) ⊆ B. Observe that H is indeed 2-vertex-connected. According to Lemma 6.18, if the number of labels is o(log∗ m), then there exist two disjoint subsets S1 and S2 in [m] such that vS1 , vS2 , and vS1 ∪S2 receive the same labels. 28

Take two copies of H with the same set of accepting certificate assignments. Denote the two copies by H1 and H2 , respectively. We construct the graph G by identifying the vertices vS1 in H1 and vS2 in H2 , call this new vertex v ∗ . Then v ∗ is a cut vertex in G. Observe that v ∗ has the same label as vS1 and vS2 , and therefore identifying these two vertices will not change the view of every other vertex than v ∗ . The view of v ∗ is identical to the view of vS1 ∪S2 in both H1 and H2 ; therefore, all vertices still output accept in G, a contradiction.

K2m

K2m S1

S2 M∥m

M

S1 vS1

vS1

vS1∪S2

vS1∪S2

vS2

vS2

M∥m

S2 M

(a) A 2-vertex-connected graph. The vertices vS1 , vS2 , and vS1 ∪S2 receive the same certificates.

(b) The graph obtained by taking two copies of the graph on the left-hand side and identifying vS1 in the first copy and vS2 in the second copy.

Figure 5: A lower bound graph for 2-vertex-connectivity. Graph (a) is an accepting instance. Vertices in graph (b) have the same view as in graph (a), while graph (b) should be rejected since the merged (white) vertex is a cut vertex. Notice that our upper bound for 2-vertex-connectivity also applies to the anonymous model. This theorem establishes a separation between bounded-degree and unbounded-degree graphs.

7

Conclusion

In this work, we present a systematic study of the local certification of k-edge/vertex-connectivity, establishing new upper and lower bounds. Our results sharpen our understanding of the landscape of what is achievable, but they also leave several intriguing questions open.

7.1

k-edge-connectivity

For k-edge-connectivity, we establish a tight bound of Θk (log n) with respect to n. However, the dependence on k is still far from being understood. In Section 3, we show that for k ≥ 3, kedge-connectivity   can be certified using O(k log n) bits, while on the lower bound side, we only log n obtain Ω k . Closing the gap between the current upper and lower bounds, in terms of their dependence on k, is an interesting direction for future work. 29

7.2

k-vertex-connectivity

√ In Section 4, we show that k-vertex-connectivity admits certificates of Õk ( n) bits under the Itai– Zehavi conjecture, while our lower bound remains Ωk (log n). Determining the correct complexity of certifying k-vertex-connectivity therefore remains a central open problem arising from this work.

7.3

Approximate local certification schemes

Censor-Hillel, Paz, and Perry [CPP20] introduced the notion of an approximation proof-labeling scheme, which distinguishes graphs satisfying a property from graphs that are far
from satisfying it. For example, they showed that certifying graph diameter ≤ k requires Ω nk bits, whereas a 2-approximation requires only O(log n) bits. Our results also have implications in this approximate setting. The lower bound constructions in Section 5 can be adapted to obtain the same lower bound for distinguishing graphs with (≥ k)edge/vertex-connectivity from those with (≤ k − 2)-edge/vertex-connectivity. Similar to how edge-connectivity is characterized by edge-disjoint spanning trees, a natural analogue for vertex-connectivity is a connected dominating set partition (CDS partition), introduced in [CGK14a]. The best known result [CGG+ 17] shows that every k-vertex-connected graph admits  a partition into Ω logk2 n connected dominating sets (CDSs). Since each CDS can be certified     using O(log n) bits, this implies that one can certify Ω logk2 n -vertex-connectivity using O logk n bits, assuming the graph is k-connected. In other words, this yields an O(log2 n)-approximation for k-vertex-connectivity. If any exact certification of k-vertex-connectivity turns out to require large certificates, is it possible to obtain significantly better approximation ratios using a small number of bits? Additionally, for edge-connectivity, following the discussion in Section 7.1 on the dependency of k in our certification scheme, it would be interested in investigating whether one can get rid of the dependency on k at the cost of approximation. Understanding this trade-off between accuracy and certificate size for connectivity remains an interesting direction for future work.

7.4

2-edge/vertex-connectivity

In Section 5, our lower bounds for k-edge- and k-vertex-connectivity are based on indistinguishability from graphs of edge or vertex connectivity at most 2. The construction has maximum degree O(k), and hence bounded degree for constant k. By contrast, Section 6 shows that on boundeddegree graphs, both 2-edge-connectivity and 2-vertex-connectivity admit constant-bit certification schemes. This sharp contrast points to a qualitative difference between certifying 2-connectivity and certifying k-connectivity for k ≥ 3. For 2-edge-connectivity, we extend the constant-bit upper bound from bounded-degree graphs to bounded-expansion graphs. Our approach builds on the pseudoforest certification scheme of Bousquet, Feuilloley, Valenzuela, and Zeitoun [BFV+ 26], which relies on constant conflict-free colorings. Since such colorings may require Ω(log n) bits on general graphs, pushing this approach substantially further appears challenging. For 2-vertex-connectivity, we prove a superconstant lower bound in the anonymous model; whether a similar lower bound holds in the ID-based setting remains open. More broadly, the certification complexity of 2-connectivity is still far from settled. Determining the optimal complexities of certifying 2-edge-connectivity and 2-vertex-connectivity, and whether the two problems are inherently different, are natural directions for future work.

30

Acknowledgment ChatGPT was used during the research stage to assist with identifying relevant literature. It was also used during manuscript preparation to polish text and refine figures. The AI tool was not used to generate the exposition of the paper.

References [AT85]

N. Alon and M. Tarsi. Covering multigraphs by simple circuits. SIAM Journal on Algebraic Discrete Methods, 6(3):345–350, 1985. doi: 10.1137/0606035. eprint: https: //doi.org/10.1137/0606035. url: https://doi.org/10.1137/0606035.

[BC25]

Dan Alden Baterisna and Yi-Jun Chang. Optimal local certification on graphs of bounded pathwidth. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 99–109, 2025.

[BFP24]

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local certification of graph decompositions and applications to minor-free classes. Journal of Parallel and Distributed Computing, 193:104954, 2024. issn: 0743-7315.

[BFV+ 26]

Nicolas Bousquet, Laurent Feuilloley, Jorge Valenzuela, and Sébastien Zeitoun. The local complexity of certifying parity, 2026. arXiv: 2606.04934 [cs.DC]. url: https: //arxiv.org/abs/2606.04934.

[BFZ25]

Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Local certification of local properties: tight bounds, trade-offs, and new parameters. SIAM Journal on Discrete Mathematics, 39(4):1974–2002, 2025. doi: 10.1137/24M1650041. eprint: https:// doi.org/10.1137/24M1650041. url: https://doi.org/10.1137/24M1650041.

[BS74]

J. A. Bondy and M. Simonovits. Cycles of even length in graphs. Journal of Combinatorial Theory, Series B, 16(2):97–105, 1974. issn: 0095-8956. doi: https://doi. org/10.1016/0095- 8956(74)90052- 5. url: https://www.sciencedirect.com/ science/article/pii/0095895674900525.

[CCD+ 24]

Shashwat Chandra, Yi-Jun Chang, Michal Dory, Mohsen Ghaffari, and Dean Leitersdorf. Fast broadcast in highly connected networks. In Kunal Agrawal and Erez Petrank, editors, Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 331–343. ACM, 2024.

[CGG+ 17]

Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, and Fabian Kuhn. Tight bounds on vertex connectivity under sampling. ACM Trans. Algorithms, 13(2), May 2017. issn: 1549-6325. doi: 10 . 1145 / 3086465. url: https : //doi.org/10.1145/3086465.

[CGK14a]

Keren Censor-Hillel, Mohsen Ghaffari, and Fabian Kuhn. A new perspective on vertex connectivity. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, pages 546–561, Portland, Oregon. Society for Industrial and Applied Mathematics, 2014. isbn: 9781611973389.

[CGK14b]

Keren Censor-Hillel, Mohsen Ghaffari, and Fabian Kuhn. Distributed connectivity decomposition. In Magnús M. Halldórsson and Shlomi Dolev, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 156–165. ACM, 2014.

31

[CKM25]

Linda Cook, Eun Jung Kim, and Tomáš Masařı́k. A tight meta-theorem for LOCAL certification of MSO2 properties within bounded treewidth graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 110– 120, Hotel Las Brisas Huatulco, Huatulco, Mexico. Association for Computing Machinery, 2025. isbn: 9798400718854. doi: 10.1145/3732772.3733562. url: https: //doi.org/10.1145/3732772.3733562.

[CLY06]

Sean Curran, Orlando Lee, and Xingxing Yu. Finding four independent trees. SIAM Journal on Computing, 35(5):1023–1058, 2006. doi: 10 . 1137 / S0097539703436734. eprint: https://doi.org/10.1137/S0097539703436734. url: https://doi.org/ 10.1137/S0097539703436734.

[CM88]

Joseph Cheriyan and S. N. Maheshwari. Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J. Algorithms, 9(4):507–537, 1988. doi: 10.1016/0196- 6774(88)90015- 6. url: https://doi.org/10.1016/01966774(88)90015-6.

[CPP20]

Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. Theoretical Computer Science, 811:112–124, 2020. issn: 0304-3975. doi: https : / / doi.org/10.1016/j.tcs.2018.08.020. url: https://www.sciencedirect.com/ science/article/pii/S030439751830536X. Special issue on Structural Information and Communication Complexit.

[CPT20]

Julia Chuzhoy, Merav Parter, and Zihan Tan. On packing low-diameter spanning trees. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of LIPIcs, 33:1–33:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

[CT18]

Keren Censor-Hillel and Tariq Toukan. On fast and robust information spreading in the vertex-congest model. Theoretical Computer Science, 751:74–90, 2018.

[CT91]

Joseph Cheriyan and Ramakrishna Thurimella. Algorithms for parallel k-vertex connectivity and sparse certificates. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC ’91, pages 391–401, New Orleans, Louisiana, USA. Association for Computing Machinery, 1991. isbn: 0897913973. doi: 10.1145/103418.103460. url: https://doi.org/10.1145/103418.103460.

[DEM+ 21]

Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Distributed weighted min-cut in nearly-optimal time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 1144–1153, Virtual, Italy. Association for Computing Machinery, 2021. isbn: 9781450380539. doi: 10.1145/3406325.3451020. url: https://doi.org/10.1145/3406325.3451020.

[DHK+ 11]

Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, pages 363–372, San Jose, California, USA. Association for Computing Machinery, 2011. isbn: 9781450306911. doi: 10 . 1145/1993636.1993686. url: https://doi.org/10.1145/1993636.1993686.

32

[DHN+ 19]

Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak. Distributed edge connectivity in sublinear time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 343–354, Phoenix, AZ, USA. Association for Computing Machinery, 2019. isbn: 9781450367059. doi: 10 . 1145 / 3313276 . 3316346. url: https : / / doi . org / 10 . 1145 / 3313276 . 3316346.

[Edm73]

Jack Edmonds. Edge-disjoint branchings. In R. Rustin, editor, Combinatorial Algorithms (Courant Computer Science Symposium 9), pages 91–96. Academic Press, New York, 1973.

[EL22]

Louis Esperet and Benjamin Lévêque. Local certification of graphs on surfaces. Theoretical Computer Science, 909:68–75, 2022.

[FFM+ 20]

Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certification of planar graphs. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC ’20, pages 319–328, Virtual Event, Italy. Association for Computing Machinery, 2020. isbn: 9781450375825. doi: 10.1145/3382734.3404505. url: https://doi.org/10.1145/ 3382734.3404505.

[FFM+ 23]

Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Local certification of graphs with bounded genus. Discrete Applied Mathematics, 325:9–36, 2023. issn: 0166-218X. doi: https://doi.org/10.1016/j. dam.2022.10.004. url: https://www.sciencedirect.com/science/article/pii/ S0166218X22003833.

[FMR+ 24]

Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A metatheorem for distributed certification. Algorithmica, 86(2):585–612, 2024.

[GK13]

Mohsen Ghaffari and Fabian Kuhn. Distributed minimum cut approximation. In Yehuda Afek, editor, Distributed Computing, pages 1–15, Berlin, Heidelberg. Springer Berlin Heidelberg, 2013. isbn: 978-3-642-41527-2.

[GN18]

Mohsen Ghaffari and Krzysztof Nowicki. Congested clique algorithms for the minimum cut problem. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, pages 357–366, Egham, United Kingdom. Association for Computing Machinery, 2018. isbn: 9781450357951. doi: 10.1145/3212734.3212750. url: https://doi.org/10.1145/3212734.3212750.

[GN20]

Mohsen Ghaffari and Krzysztof Nowicki. Massively parallel algorithms for minimum cut. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC ’20, pages 119–128, Virtual Event, Italy. Association for Computing Machinery, 2020. isbn: 9781450375825. doi: 10.1145/3382734.3405737. url: https://doi.org/ 10.1145/3382734.3405737.

[GNT20]

Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster algorithms for edge connectivity via random 2-out contractions. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA). 2020, pages 1260–1279. doi: 10.1137/ 1 . 9781611975994 . 77. eprint: https : / / epubs . siam . org / doi / pdf / 10 . 1137 / 1 . 9781611975994 . 77. url: https : / / epubs . siam . org / doi / abs / 10 . 1137 / 1 . 9781611975994.77.

33

[GP25]

Yuval Gil and Merav Parter. New Distributed Interactive Proofs for Planarity: A Matter of Left and Right. In Dariusz R. Kowalski, editor, 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), 34:1–34:23, Dagstuhl, Germany. Schloss Dagstuhl – LeibnizZentrum für Informatik, 2025. isbn: 978-3-95977-402-4. doi: 10.4230/LIPIcs.DISC. 2025 . 34. url: https : / / drops . dagstuhl . de / entities / document / 10 . 4230 / LIPIcs.DISC.2025.34.

[GP26]

Yuval Gil and Merav Parter. Distributed interactive proofs for planarity with logstar communication. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 899–924. SIAM, 2026.

[GRS91]

Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. Ramsey theory. John Wiley & Sons, 1991.

[GS16]

Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(19):1–33, 2016. doi: 10.4086/toc.2016.v012a019. url: https://theoryofcomputing.org/articles/v012a019.

[GZ22]

Mohsen Ghaffari and Goran Zuzic. Universally-optimal distributed exact min-cut. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, pages 281–291, Salerno, Italy. Association for Computing Machinery, 2022. isbn: 9781450392624. doi: 10.1145/3519270.3538429. url: https://doi.org/10. 1145/3519270.3538429.

[HPY22]

Yael Hitron, Merav Parter, and Eylon Yogev. Broadcast CONGEST algorithms against eavesdroppers. In Christian Scheideler, editor, Proceedings of the 36th International Symposium on Distributed Computing (DISC), volume 246 of LIPIcs, 27:1–27:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. url: https://doi.org/10. 4230/LIPIcs.DISC.2022.27.

[IR88]

Alon Itai and Michael Rodeh. The multi-tree approach to reliability in distributed networks. Inf. Comput., 79(1):43–59, 1988. doi: 10.1016/0890- 5401(88)90016- 8. url: https://doi.org/10.1016/0890-5401(88)90016-8.

[Jae79]

F. Jaeger. Flows and generalized coloring theorems in graphs. Journal of Combinatorial Theory, Series B, 26(2):205–216, 1979. issn: 0095-8956. doi: https://doi.org/10. 1016/0095- 8956(79)90057- 1. url: https://www.sciencedirect.com/science/ article/pii/0095895679900571.

[JMR22]

Benjamin Jauregui, Pedro Montealegre, and Ivan Rapaport. Distributed interactive proofs for the recognition of some geometric intersection graph classes. In International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 212–233. Springer, 2022.

[KKP05]

Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC ’05, pages 9–18, Las Vegas, NV, USA. Association for Computing Machinery, 2005. isbn: 1581139942. doi: 10.1145/1073814.1073817. url: https: //doi.org/10.1145/1073814.1073817.

[KN96]

Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, Cambridge, 1996.

[Men27]

K. Menger. Zur allgemeinen kurventheorie. German. Fund. Math., 10:96–115, 1927. 34

[MRR21]

Pedro Montealegre, Diego Ramı́rez-Romero, and Ivan Rapaport. Compact distributed interactive proofs for the recognition of cographs and distance-hereditary graphs. In International Symposium on Stabilizing, Safety, and Security of Distributed Systems (SSS), pages 395–409. Springer, 2021.

[Nas60]

C. St. J. A. Nash-Williams. On orientations, connectivity and odd-vertex pairings in finite graphs. Canadian Journal of Mathematics, 12:555–567, 1960.

[NI92]

Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph. Algorithmica, 7:583–596, 1992. url: https://api.semanticscholar.org/CorpusID:35970274.

[NPY20]

Moni Naor, Merav Parter, and Eylon Yogev. The power of distributed verifiers in interactive proofs. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, pages 1096–1115, Salt Lake City, Utah. Society for Industrial and Applied Mathematics, 2020.

[NS14]

Danupon Nanongkai and Hsin-Hao Su. Almost-tight distributed minimum cut algorithms. In Fabian Kuhn, editor, Distributed Computing, pages 439–453, Berlin, Heidelberg. Springer Berlin Heidelberg, 2014. isbn: 978-3-662-45174-8.

[Rob39]

H. E. Robbins. A theorem on graphs, with an application to a problem of traffic control. The American Mathematical Monthly, 46(5):281–283, 1939. doi: 10.2307/2303897.

[SE83]

Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362–391, 1983. issn: 0022-0000. doi: https : / / doi . org / 10 . 1016 / 0022 - 0000(83 ) 90006 - 5. url: https : / / www . sciencedirect.com/science/article/pii/0022000083900065.

[Set98]

Yudi Setyawan. Combinatorial Number Theory: Results of Hilbert, Schur, Folkman, and Hindman. Simon Fraser University, 1998.

[ZI89]

Avram Zehavi and Alon Itai. Three tree-paths. Journal of Graph Theory, 13(2):175– 188, 1989. doi: https : / / doi . org / 10 . 1002 / jgt . 3190130205. eprint: https : / / onlinelibrary . wiley . com / doi / pdf / 10 . 1002 / jgt . 3190130205. url: https : //onlinelibrary.wiley.com/doi/abs/10.1002/jgt.3190130205.

35