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 \(\mathcal{P}\) to be certified. In a local certification scheme [1], 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 acceptor reject.

The scheme must satisfy the following completeness and soundness guarantees:

Completeness:

If \(G\) satisfies \(\mathcal{P}\), then there exists a labeling under which every vertex accepts.

Soundness:

If \(G\) does not satisfy \(\mathcal{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\ge 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 [2]. They showed that \(k\)-vertex-connectivity, for \(k\le 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, [2] 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 [3]–[6], which include fundamental families such as planar graphs and bounded-treewidth graphs.

The next challenge is to go beyond \(3\)-vertex-connectivity. Indeed, [2] explicitly asked for efficient local certification schemes for higher vertex connectivity [2]:

Such schemes could open the door to extending this approach to more complicated minor-closed classes and larger excluded minors. At the same time, it is equally important to understand whether logarithmic label size is necessary. In this direction, [2] posed the following question [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.

Connectivity is also a key resource in the design of distributed algorithms themselves. For example, [7] 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 \(\lambda\) in \(O(((n+q)/\lambda)\log n)\) rounds. Since the vertices do not know \(\lambda\) 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 [8]–[10], and a separate line of work studies algorithms whose guarantees depend explicitly on the vertex connectivity of the underlying graph [11]–[13].

1.1 Our results↩︎

We begin by showing that, for every \(k \ge 3\), certifying \(k\)-vertex-connectivity or \(k\)-edge-connectivity requires per-vertex labels of size \(\Omega((\log n)/k)\) ([thm:32k-conn-lower]). This answers [2] in the affirmative for every constant \(k \ge 3\). Moreover, for constant \(k\), the lower bound already holds on bounded-degree graphs, that is, graphs whose maximum degree \(\Delta\) 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 [thm:322-edge-conn] and [thm:322-vertex-conn], on bounded-degree graphs, both \(2\)-edge-connectivity and \(2\)-vertex-connectivity can be certified using only a constant number of bits per vertex.

Our second result is a matching upper bound for \(k\)-edge-connectivity ([thm:32k-ec]). Together with [thm:32k-conn-lower], this gives tight bounds for certifying \(k\)-edge-connectivity for every constant \(k \ge 3\).

The certification scheme in [thm:32k-ec] uses a unified construction for all \(k \ge 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 \((v,u)\), obtaining a directed graph \(\vec{G}\), and apply Edmonds’ branching theorem [14]. This yields a single construction that works for arbitrary \(k\).

This contrasts with prior work [2], 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.

Our third result is an \(O(k^3\sqrt{n}\log^{2.5} n)\) upper bound for \(k\)-vertex-connectivity ([thm:32k-vc-cert]). The result is unconditional for \(k=4\), and for every \(k \ge 5\) it holds assuming the Itai–Zehavi conjecture [15]. This conjecture states that an undirected graph \(G\) is \(k\)-vertex-connected if and only if, for every choice of vertex \(r\in V(G)\), there exist \(k\) independent spanning trees rooted at \(r\). Here, independence means that, for every \(x\in V(G)\setminus\{r\}\), the \(r\)-to-\(x\) paths in the \(k\) trees are internally vertex-disjoint.

The best previous result [2] gives \(O(\log n)\)-bit local certification schemes for \(2\)- and \(3\)-vertex-connectivity, using open ear decompositions and Mondshein sequences, while the case \(k\ge 4\) was left open as [2]. We make progress on this open problem by giving the first local certification schemes for \(k\ge 4\): unconditionally for \(k=4\), and for all \(k\ge 5\) under the Itai–Zehavi conjecture.

Our lower bound in [thm:32k-conn-lower] applies only for \(k\ge 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 bounded-degree graphs, planar graphs, and, more generally, every proper minor-closed graph class.

Together with [thm:32k-conn-lower], these results reveal a sharp complexity gap between \(k=2\) and \(k\ge 3\) on bounded-degree graphs.

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 [16]. The construction inherently exploits the absence of unique identifiers and therefore does not extend to the setting with unique identifiers.

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 1 and 2.

1.2 Technique overview↩︎

We present a technical overview of our proofs.

1.2.0.1 Lower-bound technique for \(k\ge 3\).

Our lower bound follows the cut-and-plug framework of Göös and Suomela [17]. The graph-theoretic task is to find, for each property \(\mathcal{P}\), a witness graph \(G\in\mathcal{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 \(G_1\) and \(G_2\) of \(G\), with corresponding edges \(\{u_1,v_1\}\) and \(\{u_2,v_2\}\). Both \(G_1\) and \(G_2\) satisfy \(\mathcal{P}\), so there are labelings under which all vertices accept. The cut-and-plug operation starts from the vertex-disjoint union \(G_1 \uplus G_2\), deletes the two edges \(\{u_1,v_1\}\) and \(\{u_2,v_2\}\), and adds the cross edges \(\{u_1,v_2\}\) and \(\{u_2,v_1\}\). For our witness graphs, this edge-swapped union no longer satisfies \(\mathcal{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\ge 3\), contradicting soundness.

This also explains why the strategy is tight with respect to \(k=2\): the obstruction produced 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_\Delta(1)\)-bit certificates.

1.2.0.2 Upper-bound technique for edge connectivity.

For the upper bound on \(k\)-edge-connectivity, we move from the undirected graph \(G\) to the directed graph \(\vec{G}\) obtained by replacing each edge \(\{u,v\}\) with the two antiparallel arcs \((u,v)\) and \((v,u)\). The key observation is that \(G\) is \(k\)-edge-connected if and only if \(\vec{G}\) is \(k\)-arc-strongly connected. We can then apply Edmonds’ branching theorem [14], 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\).

1.2.0.3 Upper-bound technique for vertex connectivity.

For the upper bound for \(k\)-vertex-connectivity, 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 \(T_1\) and \(T_2\), 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 short-segment vertices appear along any root-to-vertex path. This yields an \(\widetilde{O}(\sqrt{n})\)-bit certificate 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 \(T_1\) and \(T_2\) rooted at the same vertex \(r\) such that any local certification scheme for verifying that \(T_1\) and \(T_2\) are independent requires per-vertex label size \(\Omega(\sqrt{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\sqrt{n}\log^{2.5} n)\) per-vertex label size.

1.2.0.4 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 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_\Delta(1)\) overhead [16]. 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 \(2\)-edge-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\ge 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 [18], bounded-treewidth graphs [3], [19], planar graphs and their variants [5], [20]–[22], bounded-genus graphs [6], cographs [23], distance-hereditary graphs [23], and geometric intersection graphs [24].

[17] 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 \(\Omega(\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 \(\Theta(\log n)\). There are also graph properties with certification complexity \(\operatorname{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 \(\tilde{\Omega}(\sqrt{n}+{D})\) rounds [25], [26], where the lower bound also holds for any constant-approximation. In [26], they proposed a \((2+\epsilon)\)-approximation algorithm that almost matches the lower bound; the approximation ratio was later improved to \((1+\epsilon)\) by [27]. For exact min-cut, [28] improved the complexity of [29] and provided the first sublinear algorithm; the worst-case optimal round complexity \(\tilde{O}(\sqrt{n}+{D})\) was achieved in [30], matching the lower bound. Later on, a universal optimal algorithm for exact min-cut was proposed by [31]. The min-cut problem is also studied in other related models, such as congested clique [32] and massively parallel computation [33].

1.4 Paper organization↩︎

The rest of the paper is organized as follows. In 2, we discuss variants of the local certification models and review several standard certification techniques. In 3, we present our upper bound for \(k\)-edge-connectivity via Edmonds’ branching theorem. In 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 5. In 6, we study 2-edge-connectivity and 2-vertex-connectivity. Finally, in 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.

2.0.0.1 Notation.

Throughout the paper, we use \(\tilde{O}(\cdot)\), \(\tilde{\Omega}(\cdot)\), and \(\tilde{\Theta}(\cdot)\) to suppress factors of the form \(\log^{\pm 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 \(O_k(\cdot)\), \(\Omega_k(\cdot)\), and \(\Theta_k(\cdot)\). For example, the bound \(O(k^3 \sqrt{n} \log^{2.5} n)\) can be expressed as \(\tilde{O}_k(\sqrt{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 [1]. In this model, the local verifier at each vertex \(v\) has access to \(\operatorname{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\) [17]. In the second variant, vertices have no identifiers at all; this is known as the anonymous model [1], [34].

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 \(\Omega(\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 [1] for further discussion.

2.1.1 Edge certification and degeneracy↩︎

In the edge certification scheme [2], [6], 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.

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 [2], [6] for further applications.

For bounded-degree graphs with maximum degree at most \(\Delta\), 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 [16].

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.

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.

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 \(O_k(\log n)\) bits↩︎

In this section, we prove the following theorem.

For every integer \(k \ge 1\), we use the equivalence stated in 4 to certify that a simple undirected graph \(G\) is \(k\)-edge-connected. 4 may be considered as a variant of the strong orientation theorem [35], [36].

Another key certificate used by our algorithm comes from Edmonds’ branching theorem (5). We next explain how to combine 4 with 5 to obtain a local certification scheme for \(k\)-edge-connectivity for every integer \(k \ge 2\).

Suppose that \(G\) is \(k\)-edge-connected. Then, by 4, its bidirected version \(\vec{G}\) is \(k\)-arc-strongly connected. Fix a vertex \(r \in V(\vec{G})\). By Edmonds’ branching theorem, \(\vec{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 prover can construct these two collections of branchings in \(\vec{G}\) and certify their existence to the verifiers.

It remains to see why these branchings certify \(k\)-edge-connectivity of \(G\). Assume that the verifiers are convinced that \(\vec{G}\) contains the two collections of branchings described above. We claim that every nontrivial cut⁴ \((S,V(G)\setminus S)\) has at least \(k\) arcs entering \(S\) in \(\vec{G}\). If \(r \notin S\), then each out-branching contains at least one arc entering \(S\) from \(V(G)\setminus S\). Since the \(k\) out-branchings are pairwise arc-disjoint, this gives at least \(k\) arcs entering \(S\). If \(r \in S\), the same argument applied to the \(k\) in-branchings gives at least \(k\) arcs entering \(S\). Hence every nontrivial cut has at least \(k\) incoming arcs.

Therefore, after deleting any set of at most \(k-1\) arcs from \(\vec{G}\), every nontrivial cut still has at least one incoming arc. This implies that the remaining digraph is strongly connected, and hence \(\vec{G}\) is \(k\)-arc-strongly connected. By 4, \(G\) is \(k\)-edge-connected.

Conversely, if \(G\) is not \(k\)-edge-connected, then 4 implies that \(\vec{G}\) is not \(k\)-arc-strongly connected. In this case, such two collections of branchings cannot exist; otherwise, the argument above would imply that \(\vec{G}\) is \(k\)-arc-strongly connected. Hence no prover can certify the existence of these two collections to the verifiers.

Consequently, it remains for the prover to certify that, for some vertex \(r \in 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.

• Prover: Fix a vertex \(r \in V(G)\) and compute \(k\) arc-disjoint out-branchings of \(\vec{G}\) rooted at \(r\), denoted \(T_i\) for \(i \in [k]\). For each vertex \(v \in V(G)\) and each \(i \in [k]\), give the verifier for \(v\) a certificate \[c_i(v) \mathrel{\vcenter{:}}= \left(\operatorname{ID}(r),\, p_i(v),\, \operatorname{depth}_i(v)\right),\] where \(p_i(v)\) is the \(\operatorname{ID}\) of \(v\)’s parent in \(T_i\) (with \(p_i(r)\) set to a null pointer) and \(\operatorname{depth}_i(v)\) is the depth of \(v\) in \(T_i\).

• 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 \(\operatorname{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 \(\operatorname{depth}_i(r)=0\) for all \(i \in [k]\).

  • (\(T_i\) consists of \(n-1\) edges.) Each vertex \(v\) with \(\operatorname{depth}_{i}(v)>0\) checks that its parent has a smaller depth. This can be done using \(p_{i}(v)\) in the certificate of \(v\), and \(\operatorname{depth}_i(p_i(v))\) in the certificate of its parent \(p_i(v)\).

  • (\(T_i\) for \(i \in [k]\) are pairwise arc-disjoint.) Each vertex \(v \ne r\) checks whether the parent identifiers \(p_i(v)\) over all \(i \in [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 \(T_i\), and this violation would be detected by vertex \(y\).

  Given the certificates \(c_i(v)\) for all \(v \in V(G)\) and \(i \in [k]\), the verifiers can locally check that, for each \(i \in [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 \(T_i\) is connected and has exactly \(n-1\) edges, and hence is a tree. Since every arc of \(T_i\) is oriented from parent to child, so \(T_i\) is an out-branching rooted at \(r\). Finally, the verifiers can also check that the \(T_i\) are pairwise arc-disjoint. This yields an \(O(k \log n)\)-bit local certification scheme for \(k\)-edge-connectivity for every integer \(k \ge 2\).

4 Certifying \(k\)-vertex-connectivity in \(\tilde{O}_k(\sqrt{n})\) bits↩︎

To explain our upper bound for \(k\)-vertex-connectivity, we first recall the following conjecture of Itai and Zehavi [15]: a graph \(G\) is \(k\)-vertex-connected if and only if for every vertex \(r\in V(G)\), there exist \(k\) independent spanning trees rooted at \(r\).

We also recall that independence means that for every vertex \(x\in G\setminus r\), the paths from \(r\) to \(x\) in the \(k\) trees are internally vertex-disjoint. See 1 for an illustration when \(k=2\). The Itai–Zehavi conjecture is known to hold for every \(k \in \{1, 2, 3, 4\}\) [15], [38]–[40]. Using this characterization, we obtain a local certification scheme for \(k\)-vertex-connectivity with per-vertex label size \(\tilde{O}_k(\sqrt{n})\) for \(k\in\{2,3,4\}\). For \(k\ge 5\), we obtain the same upper bound assuming the Itai–Zehavi conjecture.

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 \(r_1,\ldots,r_k \in V(G)\) (rather than all vertices) such that, for each \(i \in [k]\), \(G\) contains \(k\) independent spanning trees rooted at \(r_i\). 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 \(r_1,\ldots,r_k\), 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 \(\binom{4}{2}\) 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 \ge 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 \(\tilde{O}_k(\sqrt{n})\) bits suffice to certify two independent spanning trees rooted at the same vertex.

Given this lemma, [thm:32k-vc-cert] follows directly.

4.1 is devoted to proving 6. In 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 \(\Omega(\sqrt{n})\).

4.1 Proof of 6↩︎

We first consider the following naive approach: Given two spanning trees \(T_1,T_2\) rooted at \(r\), for a vertex \(v\) to verify that the root-to-\(v\) path in \(T_1\) and the root-to-\(v\) path in \(T_2\) are internally vertex-disjoint, we provide \(v\) with the lists of its ancestors in two trees. Then, if \(T_1\) and \(T_2\) 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 \(\tilde{O}(\sqrt{n})\) via heavy-light decomposition.

In 4.1.1, we will describe the certificate assignment and its complexity; in 4.1.2, we will describe the verification algorithm and the correctness of the entire certification scheme. Then 6 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↩︎

4.1.1.1 Heavy-light decomposition and path-encoding

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.

Let \(T\) be a tree rooted at \(r\). Denote by \(\Psi(T)=\{S_1,\ldots,S_t\}\) the set of segments of the heavy-light decomposition on \(T\).

• For each vertex \(v\in T\), define \(\operatorname{seg}_T(v)=i\) if \(v\in S_i\). 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 \(S_{\operatorname{seg}_T(v)}\), denoted as \(\operatorname{rank}_T(v)=j\). We encode the position of \(v\) in \(T\) by \(\eta_T(v)=(\operatorname{seg}_T(v),\operatorname{rank}_T(v))\).

• We encode the root-to-\(v\) path, denoted by \(p_T(v)\), as follows: Suppose that the root-to \(v\) path in \(T\) overlaps with \(l\) segments \(S'_1,\ldots,S'_l\). For each \(j\in[l]\), let \(u_j\) be the vertex in \(S'_j\cap p_T(v)\) with the largest rank. We define the path-encoding of \(v\), denoted by \(\alpha_T(v)\), to be a set of segment-rank pairs, which consists of the vertex-encoding of \(u_1,\ldots,u_l\). More formally, \(\alpha_T(v)=\{(\operatorname{seg}_T(u_j), \operatorname{rank}_T(u_j)):j\in[l]\}\). Observe that the vertex-encoding of \(v\) should be the last segment-rank pair contained in \(\alpha_T(v)\), that is, \(\eta_T(v)=(\operatorname{seg}_T(u_l), \operatorname{rank}_T(u_l))\). According to 7, \(l\in O(\log n)\), and therefore the path-encoding requires \(O(\log^2n)\) bits.

For each vertex \(v\), let \(A_T(v)\) be the set of the addresses of all ancestors of \(v\) in \(T\). \(A_T(v)=\{\eta_T(w):w\in p_T(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 \(p_T(v)\), the smallest-rank vertex in the intersection always has rank \(1\). It follows that \(A_T(v)\) can be recovered directly from the path-encoding \(\alpha_T(v)\).

4.1.1.2 Certificate assignment

Observe that to certify the independence of \(T_1\) and \(T_2\), it suffices for each non-root vertex \(u\) to detect whether there exists another non-root vertex \(v\) such that \(u\in T_1(v)\cap T_2(v)\). For \(i \in \{1,2\}\), let \(-i\) be the complement of \(i\) in the set \(\{1,2\}\); we say that \(v\) is a \(T_i\)-ancestor of \(u\) if and only if \(u\in T_i(v)\). For simplicity, let \(\eta_i(v)=\eta_{T_i}(v)\) and \(\alpha_i(v)=\alpha_{T_i}(v)\). We say that \((i,\alpha_i(v))\) is the \(T_i\)-address of \(v\).

• For each vertex \(v\), for all \(i \in \{1,2\}\), include the \(T_i\)-address \((i,\alpha_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,\alpha_2(v))\) in the certificates of all the vertices in \(T_1(v)\).

  • (Option \(2\).) Include \((1,\alpha_1(v))\) in the certificates of all the vertices in \(T_2(v)\).

  In other words, for each \(i \in \{1,2\}\), each vertex \(u\) receives a list of \(T_{-i}\)-addresses of a subset of its \(T_i\)-ancestors (including itself). Denote this list by \(\Lambda_i(u)\). Let the above choice of \(v\) be \(\pi(v)\). \(\pi(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\in T_1(u)\) and \(u\in T_2(v)\), we remove some certificates based on the following rules:

  • If \(\pi(u)=\pi(v)=1\), then for every vertex \(x\in T_1(v)\), we remove \((2,\alpha_2(u))\) from \(\Lambda_1(x)\).

  • If \(\pi(u)=\pi(v)=2\), then for every vertex \(x\in T_2(u)\), we remove \((1,\alpha_1(v))\) from \(\Lambda_2(x)\).

For each \(i \in \{1,2\}\) and each segment \(S\in\Psi(T_i)\), let \(V(S)\) be the vertex set of this segment. Then, according to the cancellation rules, we have the following lemma:

Given this lemma, we now describe the rules for deciding the choice \(\pi(v)\).

• Let \(\tau\) be a threshold that will be defined later. We say that a segment is long if its length exceeds \(\tau\); otherwise, it is short. For any rooted tree \(T\), let \(\textsf{Long}(T)\) be the set of vertices that belong to some long segments in \(T\), and let \(\textsf{Short}(T)\) be the set of vertices that belong to some short segments in \(T\).

• If \(v\in\textsf{Long}(T_1)\), then \(\pi(v)=2\). Otherwise, \(\pi(v)=1\).

4.1.1.3 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,\alpha_1(v))\) occurs in the certificates of \(u\), then \(v\in\textsf{Long}(T_1)\). According to 8, the number of such \(v\) is at most the number of long segments in \(T_1\) plus one, which is \(O(\frac{n}{\tau})\).

• If \((2,\alpha_2(v))\) occurs in the certificates of \(v\), then \(\pi(v)=1\) according to our rule, and one of the following holds:

  • \(v\in\textsf{Long}(T_2)\). In this case, according to 8, the number of such \(v\) is at most the number of long segments in \(T_2\) plus one, which is \(O(\frac{n}{\tau})\).

  • Observe that if \(v\in\textsf{Short}(T_2)\) and \(\pi(v)=1\), then \(v\in\textsf{Short}(T_1)\) according to our rules. Therefore, \(v\in\textsf{Short}(T_1)\cap P_1(r,u)\). Recall that the number of short segments overlapping with the root-to-\(u\) path in \(T_1\) is at most \(O(\log n)\), and the number of such \(v\) is at most \(\tau\cdot O(\log n)\).

For each vertex \(v\) and each \(i \in \{1,2\}\), the set \(\Lambda_i(v)\) consists of \(O(\frac{n}{\tau}+\tau\cdot O(\log n))\) addresses, each of which need \(O(\log^2 n)\) bits to store. Set \(\tau=\sqrt{\frac{n}{\log n}}\), we get an \(O(\sqrt{n}\log^{2.5}n)\) size bound for our local certification scheme.

4.1.2 Verification algorithm and correctness↩︎

4.1.2.1 Verification algorithm

Recall that in our certificate assignment, for each \(i \in \{1,2\}\), each vertex \(v\) receives its own address \((i,\alpha_i(v))\), the choice \(\pi(v)\) of which subtree to send its information to, and a list \(\Lambda_i(v)\) of the \(T_{-i}\)-addresses of a set of its \(T_i\)-ancestors. We define \(|\alpha_i(v)|\) to be the number of segment-rank pairs included in \(\alpha_i(v)\), and we set \((\operatorname{seg}_i(v),\operatorname{rank}_i(v))\) to be the last segment-rank pair in \(\alpha_i(v)\)

The verification algorithm is as follows:

• The vertices check the consistency between their path-encoding. More precisely, for each \(i\in\{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 \(|\alpha_i(u)|=|\alpha_i(v)|\). Moreover, \(\alpha_i(u)\) and \(\alpha_i(v)\) differ only in the last segment-rank pair, which satisfies \(\operatorname{seg}_i(u)=\operatorname{seg}_i(v)\) and \(\operatorname{rank}_i(u)=\operatorname{rank}_i(v)+1\).

  • (Other children initiate new segments.) For every child \(w\) other than \(u\), \(|\alpha_i(w)|=|\alpha_i(v)|+1\). Moreover, \(\alpha_i(w)=\alpha_i(v)\cup\{(\operatorname{seg}_i(w),\operatorname{rank}_i(w))\}\), and \(\operatorname{rank}_i(w)=1\).

• Each vertex checks that the certificate assignments respect our rules. More specifically, for each \(i \in \{1,2\}\), each non-leaf vertex \(v\) checks the following:

  • (The two options.) Each vertex checks that either \(\pi(v)=2\) and \(\alpha_1(v)\in\Lambda_2(v)\), or \(\pi(v)=1\) and \(\alpha_2(v)\in\Lambda_1(v)\).

  • (The cancellation rules.) For each child \(x\in T_i(v)\), the lists of the addresses \(\Lambda_i(v)\) and \(\Lambda_i(x)\) satisfy the following: (\(1.\)) \(x\)’s \(T_{-i}\)-address does not appear in \(\Lambda_i(v)\), that is, \(\alpha_{-i}(x)\not\in\Lambda_i(v)\); and (\(2.\)) if there exists \(u\) such that \(\alpha_{-i}(u)\in\Lambda_i(v)\setminus\Lambda_i(x)\), then \(x\) must be a \(T_{-i}\)-ancestor of \(u\) and \(\pi(x)=i\). This can be checked by the path encoding in \(\alpha_{-i}(u)\) and the \(T_{-i}\)-address of \(x\).

  If any check fails, vertex \(v\) outputs reject.

• For each vertex \(v\) and each \(i \in \{1,2\}\), if there exists a label \((i,\alpha_i(u))\) in the certificate for some \(u\neq v\) such that \(\eta_i(u)\in A_i(v)\), then output reject.

• The vertex outputs acceptif all the above verification passes.

4.1.2.2 Correctness

Suppose that \(T_1\) and \(T_2\) are not independent, then there exists vertices \(u,v\) such that \(v\in T_1(u)\cap T_2(u)\). We assume \(\pi(u)=1\) without loss of generality. Let \(w\) be the vertex with the largest rank in \(T_1\) that satisfies \(\pi(w)=1\), \(u\in T_2(w)\) and \(v\in T_1(w)\). Such a vertex \(w\) exists since we can take \(w=u\). \(w\neq v\) since otherwise \(v\in T_1(u)\cap T_2(u)\) and \(u\in T_2(w)\) will give us a contradiction to the fact that \(T_{-i}\) is a tree.

We claim that \((2,\alpha_2(w))\) must be added to the set \(\Lambda_1(v)\). Suppose not, since \(\pi(w)=1\), \((2,\alpha_2(w))\in\Lambda_1(w)\), we can find two vertices \(y,z\) along the \(w\)–\(v\) path in \(T_1\) such that \(y\) is the parent of \(z\) and \((2,\alpha_2(w))\in\Lambda_1(y)\setminus\Lambda_1(z)\). According to our verification algorithm, this means that \(z\) must be an \(T_2\)-ancestor of \(w\) and \(\pi(z)=i\), otherwise \(y\) will output reject. However, \(z\) has a larger rank than \(w\) in \(T_i\), contradicting the way we chose \(w\).

Since \(v\in T_1(u)\cap T_1(w)\), \(v\in T_2(u)\) and \(u\in T_2(w)\), we have \(v\in T_1(w)\cap T_2(w)\). According to our path encoding, \(w\) belongs to \(A_2(v)\), and \(v\) will detect that \(\eta_2(w)\in A_2(v)\) with the certificates \(\alpha_2(w)\) and \(\alpha_2(v)\), which make \(v\) output rejectaccording to our verification algorithm.

4.2 Lower bound for certifying two independent spanning trees↩︎

Since the upper bound for \(k\)-vertex-connectivity is \(\tilde{O}_k(\sqrt{n})\), while the lower bound we get in 5 is \(\Omega_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 \(\Omega(\sqrt{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.

In 4.2.1, we will discuss the background about two-party communication complexity, and in 4.2.2, we will give the proof of the lower bound.

4.2.1 Two-party communication complexity↩︎

4.2.1.1 The Set-Disjointness problem

Let \(x,y\in\{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\in[s]\) such that \(x_i=y_i=1\). The truth value of whether \(x\) and \(y\) are disjoint is denoted as \(\textsf{DISJ}(x,y)\). The two-party communication problem of Set-Disjointness (\(\textsf{DISJ}\)) is defined as follows. Two players called Alice and Bob, are given inputs \(x,y\in\{0,1\}^s\) respectively, and they communicate via a deterministic protocol to decide whether \(\textsf{DISJ}(x,y)=\text{\small\texttt{TRUE}}\) or \(\textsf{DISJ}(x,y)=\text{\small\texttt{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 \(\textsf{DISJ}\) is the minimum cost among all the protocols.

4.2.1.2 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 \(\text{\small\texttt{TRUE}}\)-instance, there exists an advising string such that the players output accept.

• For each \(\text{\small\texttt{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\).

For example, the nondeterministic communication complexity of \(\overline{\textsf{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 \(\textsf{DISJ}\) is \(\Omega(s)\).

4.2.2 Lower-bound construction↩︎

Let \(s\) be an integer. For every instance \((x,y)\) of a Set-Disjointness problem over \(s^2\) elements, we define an instance \(G_{x,y}\) on \(n=(2(s+1)s+5)\) vertices. See 3 for an illustration.

• The underlying graph is constructed as follows:

  • The vertex set \(V(G)=A\cup B\cup P\cup Q\cup\{v_1,v_2,u_1,u_2,r\}\), where \(A=\{a_{i,j} : i,j\in[s]\}\), \(B=\{b_{i,j} : i,j\in[s]\}\), \(P=\{p_j:j\in[s]\}\), and \(Q=\{q_i:i\in[s]\}\).

  • \(A\) forms a grid-like structure where each column is a clique of size \(s\): For each \(j\in[s]\), let \(A_j=\{a_{i,j}:i\in[s]\}\), then \(A_j\) induces a \(K_s\). For each \(i\in[s]\), \(\{a_{i,j},a_{i,j+1}\}\in E(G)\) for all \(j\in[s-1]\).

  • \(B\) forms a grid-like structure where each row is a clique of size \(s\): For each \(i\in[s]\), let \(B_i=\{b_{i,j}:j\in[s]\}\), then \(B_i\) induces a \(K_s\). For each \(j\in[s]\), \(\{b_{i,j},b_{i+1,j}\}\in E(G)\) for all \(i\in[s-1]\).

  • For each \(j\in[s]\), the vertex \(p_j\) is connected to each vertex in \(A_j\cup\{b_{1,j}\}\) with an edge. For each \(i\in[s]\), the vertex \(q_i\) is connected to each vertex in \(B_i\cup\{a_{i,s}\}\) with an edge.

  • The vertex \(v_1\) is connected to each vertex in \(P\cup\{v_2,r\}\) with an edge, and \(v_2\) is connected to each vertex in \(A\cup\{v_1,r\}\) with an edge. The vertex \(u_1\) is connected to each vertex in \(B\cup Q\cup\{u_2,r\}\), and \(u_2\) is connected to each vertex in \(Q\cup B_s\cup\{u_1,r\}\).

• The two spanning trees on the graph \(G_{x,y}\) are constructed as follows:

  • For each \(i\in[s]\), \((a_{i,j},a_{i,j+1})\in T_1\) for all \(i\in[s-1]\) and \((a_{i,s},q_i)\in T_1\). For each \(j\in[s]\), \((p_j,v_1)\in T_1\). Also, \((v_1,r)\in T_1\) and \((u_1,r)\in T_1\).

  • For each \(j\in[s]\), \((b_{i,j},b_{i+1,j})\in T_2\) for all \(i\in [s-1]\) and \((p_j,b_{1,j}),(b_{s,j},u_2)\in T_2\). For each \(i\in[s]\), \((q_i,u_2)\in T_2\). Also, \((v_2,r)\in T_2\) and \((u_2,r)\in T_2\).

  • For each \(i,j\in[s]\), if \(x_{i,j}=0\), then \((a_{i,j},v_2)\in T_2\). For each \(j\in[s]\), let \(A'_j=A_j\cap\{a_{i,j}:x_{i,j}=1\}\). Let \(|A'_j|=\nu_j\), for each \(t\in[\nu_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])\in T_2\) for all \(t\in\{2,\ldots,\nu_j\}\) and \((A'_j[1],p_j)\in T_2\).

  • For each \(i,j\in[s]\), if \(y_{i,j}=0\), then \((b_{i,j},u_1)\in T_1\). For each \(i\in[s]\), let \(B'_i=B_i\cap\{b_{i,j}:y_{i,j}=1\}\). Let \(|B'_i|=\mu_i\), for each \(t\in[\mu_i]\), denote by \(B'_i[t]\) the \(t\)-th element in \(B'_i\) sorted by the \(j\)-index. Then \((q_i,B'_i[1])\in T_1\), \((B'_i[t-1],B'_i[t])\in T_1\) for all \(t\in\{2,\ldots,\mu_i\}\), and \((B'_i[\mu_i],u_1)\in T_1\).

5 Lower bounds for \(k\)-connectivity for any \(k\ge3\)↩︎

In this section, we prove that for any \(k\ge 3\), certifying \(k\)-vertex-connectivity and \(k\)-edge-connectivity both require \(\Omega((\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 \(\operatorname{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 \(H_1\) and \(H_2\) where the local views of the special edges \(\{u_1,v_1\}\) and \(\{u_2,v_2\}\) are the same. Then one can apply the cut-and-plug technique to create a new connected graph with doubled size from \(H_1\) and \(H_2\), where edges \(\{u_1,v_1\}\) and \(\{u_2,v_2\}\) are “kicked out” and \(u_1\) is reconnected to \(v_2\) while \(u_2\) is reconnected to \(v_1\). 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 [17], they use a slightly more complicated cut-and-plug technique and prove several \(\Omega(\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 4 for a visualization. To describe and prove this lemma, we need some more notations. A graph property \(\mathcal{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\in G\), denote by \(N(v)\) the neighbors of \(v\) in \(G\) (not including \(v\)). We use \(\operatorname{ID}(v)\) to represent the identifier of \(v\).

Now we apply 11 to prove lower bounds for certifying \(k\)-connectivity.

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 [thm:322-conn].

We split [thm:322-conn] into three propositions and prove them separately in the following subsections. In 6.1.1 ([thm:322-edge-conn]), we give a constant-bit local certification scheme for \(2\)-edge-connectivity in bounded degree graphs. In 6.1.2 ([thm:322-vertex-conn]), 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 6.1.3 ([thm:322-ec-bdd-expansion]), 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.

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.

Our first observation is that \(2\)-edge-connectivity admits a constant-bit edge-certification scheme via a simple application of 13.

[thm:322-edge-conn] then follows immediately by a transformation from edge-certification to vertex-certification.

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.

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.

6.1.2.1 Transforming a \(2\)-vertex-connected graph into a \(2\)-edge-connected graph

Given a \(2\)-vertex-connected graph \(G=(V,E)\), we construct a graph \(G'=(V',E')\) by the following operation:

• For each vertex \(v\in G\), make it into a super vertex \(\psi(v)=\{v_0,v_1\}\). Add the vertices \(v_0,v_1\) to \(V'\), and add an edge \(\{v_0,v_1\}\) to \(E'\).

• For each vertex \(v\in G\), partition \(N(v)\), the neighborhood of \(v\), into two non-empty subsets \(N_0(v),N_1(v)\).

• For each pair of vertices \(\{u,v\}\in E\) and \(i,j\in\{0,1\}\), add an edge \(\{u_i,v_j\}\) to \(E'\) if and only if \(v\in N_i(u)\) and \(u\in N_j(v)\).

According to the rules of how we construct \(G'\), we have the following observation:

We claim that if the original graph \(G\) is \(2\)-vertex-connected, then the resulting graph \(G'\) is \(2\)-edge-connected.

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 ([thm:322-edge-conn]) 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.

Before proving [thm:322-ec-bdd-expansion], we first provide some intuition and review the necessary graph-theoretic background.

Our approach again builds on the edge certification scheme in [lem:322-ec-EdgeCert]. The main obstacle was that when the degree is unbounded, transforming edge-certification schemes to vertex-certification schemes requires vertices to know which edges it is simulating, which is precisely what gives rise to the additive \(\Theta(\log n)\) term in 2. We show that for bounded expansion graphs, this obstacle can be overcome via an application of a very recent certification scheme for pseudoforest [16].

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 [16], 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.

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\in[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.

Combining with the edge-certification scheme for \(2\)-edge-connectivity in [lem:322-ec-EdgeCert], we derive the following lemma.

Our main idea is to use the pseudoforest certification scheme of 17 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 [lem:322-ec-EdgeCert] 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 17, 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 \(G\) is a subset of edges \(E'\subseteq E\) such that the subgraph \(G'=(V,E')\) is \(k\)-edge-connected (\(k\)-vertex-connectivity, 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\) [45], [46] by finding BFS (breadth-first search) spanning forest iteratively.

Intuitively, letting \(k=2\), we can use 17 to encode the sparse certificate in 20 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.

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.

Now we are ready to prove [thm:322-ec-bdd-expansion].

6.2 An \(\omega(1)\) lower bound for \(2\)-vertex-connectivity in the anonymous model↩︎

In contrast to the constant-size certification scheme for bounded-degree graphs in [thm:322-vertex-conn], 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 [16] with the observation that their accepting instance can be made \(2\)-vertex-connected. See 5 for an illustration.

To prove [thm:322-vc-lb], we use the same approach as in [16]. The following lemma is an implication of the Finite Union Theorem (see [16] and the reference therein) and Lemma 15 in [16].

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 \(\Theta_k(\log n)\) with respect to \(n\). However, the dependence on \(k\) is still far from being understood. In 3, we show that for \(k \ge 3\), \(k\)-edge-connectivity can be certified using \(O(k \log n)\) bits, while on the lower bound side, we only obtain \(\Omega\!\left(\frac{\log n}{k}\right)\). Closing the gap between the current upper and lower bounds, in terms of their dependence on \(k\), is an interesting direction for future work.

7.2 \(k\)-vertex-connectivity↩︎

In 4, we show that \(k\)-vertex-connectivity admits certificates of \(\tilde{O}_k(\sqrt{n})\) bits under the Itai–Zehavi conjecture, while our lower bound remains \(\Omega_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↩︎

[50] 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 \(\le k\) requires \(\Omega\!\left(\frac{n}{k}\right)\) 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 5 can be adapted to obtain the same lower bound for distinguishing graphs with \((\ge k)\)-edge/vertex-connectivity from those with \((\le 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 [13]. The best known result [12] shows that every \(k\)-vertex-connected graph admits a partition into \(\Omega\!\left(\frac{k}{\log^2 n}\right)\) connected dominating sets (CDSs). Since each CDS can be certified using \(O(\log n)\) bits, this implies that one can certify \(\Omega\!\left(\frac{k}{\log^2 n}\right)\)-vertex-connectivity using \(O\!\left(\frac{k}{\log n}\right)\) bits, assuming the graph is \(k\)-connected. In other words, this yields an \(O(\log^2 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 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 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, 6 shows that on bounded-degree 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\ge 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 [16], which relies on constant conflict-free colorings. Since such colorings may require \(\Omega(\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.

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↩︎

---

1. National University of Singapore. ORCID: 0000-0002-0109-2432. Email: cyijun@nus.edu.sg↩︎

2. National University of Singapore. ORCID: 0009-0002-9754-9931. Email: r12921065@ntu.edu.tw↩︎

3. Academia Sinica. ORCID: 0000-0002-2243-8666. Email: mttsai@as.edu.tw↩︎

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