--- abstract: | Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph $G$ belongs to a given graph class $\mathcal{G}$. Such certifications with labels of size $O(\log n)$ (where $n$ is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this work, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor $H$, $H$-minor-free graphs can indeed be certified with labels of size $O(\log n)$. We also show matching lower bounds with a simple new proof technique. author: - Nicolas Bousquet - Laurent Feuilloley - Théo Pierron bibliography: - 'biblio.bib' title: 'Local certification of graph decompositions and applications to minor-free classes' --- Introduction ============ Local certification is an active field of research in the theory of distributed computing. On a high level it consists in certifying global properties in such a way that the verification can be done locally. More precisely, for a given property, a local certification consists of a labeling (called a *certificate assignment*), and of a local verification algorithm. If the configuration of the network is correct, then there should exist a labeling of the nodes that is accepted by the verification algorithm, whereas if the configuration is incorrect no labeling should make the verification algorithm accept. Local certification originates from self-stabilization, and was first concerned with certifying that a solution to an algorithmic problem is correct. However, it is also important to understand how to certify properties of the network itself, that is, to find locally checkable proofs that the network belongs to some graph class. There are several reasons for that. First, because certifying some solutions can be hard in general graphs, while they become simpler on more restricted classes. To make use of this fact, it is important to be able to certify that the network does belong to the restricted class. Second, because some distributed algorithms work only on some specific graph classes, and we need a way to ensure that the network does belong to the class, before running the algorithm. Third, the distinction between certifying solutions and network properties is rather weak, in the sense that the techniques are basically the same. So we should take advantage of the fact that a lot is known about graph classes to learn more about certification. In the domain of graph classes certification, there have been several results on various classes such as trees @KormanKP10, bipartite graphs @GoosS16 or graphs of bounded diameter @Censor-HillelPP20, but until two years ago little was known about essential classes, such as planar graphs, $H$-free or $H$-minor-free graphs. Recently, it has been shown that planar graphs and graphs of bounded genus can be certified with $O(\log n)$-bit labels @FeuilloleyFMRRT20 [@FeuilloleyFMRRT21; @EsperetL21]. This size, $O(\log n)$, is the gold standard of certification, in the sense that little can be achieved with $o(\log n)$ bits, thus $O(\log n)$ is often the best we can hope for. It happens that planar and bounded-genus graphs are classic examples of graphs classes defined by forbidden minors, which naturally raises the following question. \[@FeuilloleyFMRRT21 [@Feuilloley19]\] \[conj:minorconj\] Can any graph class defined by a finite set of forbidden minors be certified with $O(\log n)$-bit certificates? This open question is quite challenging: there are as many good reasons to believe that the answer is positive as negative. First, the literature provides some reasons to believe that the conjecture is true. Properties that are known to be hard to certify, that is, that are known to require large certificates, are very different from minor-freeness. Specifically, all these properties (*e.g.* small diameter @Censor-HillelPP20, non-3-colorability @GoosS16, having a non-trivial automorphism @GoosS16) are non-hereditary. That is, removing a node or an edge may yield a graph that is not in the class. Intuitively, hereditary properties might be easier to certify in the sense that one does not need to encode information about every single edge or node, as the class is stable by removal of edges and nodes. Minor-freeness is a typical example of hereditary property. Moreover, this property, that has been intensively studied in the last decades, is known to carry a lot of structure, which is an argument in favor of the existence of a compact certification (that is a certification with $O(\log n)$-bit labels). On the other hand, from a graph theory perspective, it might be surprising that a general compact certification existed for minor-free graphs. Indeed, for the known results, obtaining a compact certification is tightly linked to the existence of a precise constructive characterization of the class (*e.g.* a planar embedding for planar graphs @FeuilloleyFMRRT20 [@EsperetL21], or a canonical path to the root for trees @KormanKP10). While such a characterization is known for some restricted minor-closed classes, we are far from having such a characterization for every minor-closed class. Note that there are a lot of combinatorial and algorithmic results on $H$-minor free graphs, but they actually follow from properties satisfied by $H$-minor free graphs, not from exact characterizations of such graphs. For certification, we need to rule out the graphs that do not belong to the class, hence a characterization is somehow necessary. It is important to note that forbidden minor characterizations are about structures that are absent from the graphs, and local certification is often about certifying the existence of some structures, which explains why it is a challenge to certify all minor-free classes with small certificates. On the other hand, as we will see later, certifying that a minor does appear in the graph is easy. Our results ----------- An extensive line of work in structural graph theory aims to provide characterizations of classes using so-called decomposition theorems. Amongst the most famous examples of these theorems is the proof of the $4$-Color Theorem @appel1976every or the Strong Perfect Graph Theorem @chudnovsky2006strong which consists in decomposing graphs until we reach some elementary graphs. Our goal in this paper is to prove that many of these decomposition tools can actually be used in order to certify the fact that the graph belongs to the class. We first prove that several classic decomposition techniques existing in the literature are suitable for certification. We then apply these general tools on Question \[conj:minorconj\] to prove that several $H$-minor free graph classes can be certified with $O(\log n)$ bits. In particular, our results provide evidence that, if the answer to Question \[conj:minorconj\] is negative then it is certainly for large non-planar graphs $H$. The decomposition tools we are able to certify are at the core of many decomposition theorems: 2-(edge-)connectivity, 3-connectivity, block-cut trees, forbidden subgraphs, and expansions of nodes or edges by new graphs. Note that these tools are also interesting by themselves, in particular, connectivity is an important measure of robustness in networks. One common challenge in the design of certification for decomposition is what we call *certificate congestion*. Consider for example a situation in which we have a certification for $k$ graphs, and we want to merge these graphs by identifying one vertex in each of them. Then, the straightforward technique to certify the merged graph is to give to the merged node its certificate for every of these $k$ graphs. But since $k$ might be large, this implies a large certificate size. Since we aim for small certificates, we want to avoid such congestion. We use several solutions to cope with this problem. Using these tools, we show that the answer to Question \[conj:minorconj\] is positive for many small graphs. These results permit to illustrate our methods with simple and compact applications of our tools. More generally, we aim at providing some evidence that graph decomposition and these tools can be successfully used in the certification setting, and it is very likely that many other minor-closed classes can be certified using our techniques. Our main results are summarized in Figure \[fig:our-results-certification\], and illustrations of the corresponding minors can be found in Figure \[fig:minors\]. These are actually the hard cases of the following theorem. <span>theorem</span><span>ThmFourVertices</span> \[thm:4vertices\] $H$-minor-free classes can be certified in $O(\log n)$ bits when $H$ has at most 4 vertices. We also prove a general $\Omega(\log n)$ lower bounds for $H$-minor-freeness for all 2-connected graphs $H$. This generalizes and simplifies the lower bounds of @FeuilloleyFMRRT20 which apply only to $K_k$ and $K_{p,q}$-minor-free graphs, and use ad-hoc and more complicated techniques. At the end of the paper, we discuss why the current tools we have, both in terms of upper and lower bounds, do not allow settling Question \[conj:minorconj\]. We list a few key questions that we need to answer before we can fully understand the certification of minor-closed classes, from the certification of classes with no tree minors to the certification $k$-connectivity, for arbitrary $k$. <span>|c|c|c|c|</span> Class & Optimal size & Result\ $K_3$-minor free & $\Theta(\log n)$ & <span>3.0cm</span> Equivalent to\ acyclicity @KormanKP10 [@GoosS16]. \ Diamond-minor-free & $\Theta(\log n)$ & Corollary \[coro:diamond-etc\]\ $K_4$-minor-free & $\Theta(\log n)$ & Corollary \[coro:diamond-etc\]\ $K_{2,3}$-minor-free & $\Theta(\log n)$ & Corollary \[coro:diamond-etc\]\ <span>3.5cm</span> $(K_{2,3},K_4)$-minor-free\ (*i.e.* outerplanar) & $\Theta(\log n)$ & Corollary \[coro:diamond-etc\]\ $K_{2,4}$-minor-free & $\Theta(\log n)$ & Lemma \[lem:2-connected-K24\]\ \[thick,v/.style=<span>draw, circle, minimum size=10pt</span>\] (A) at (0,0.5) ; (B) at (0,-0.5) ; (C) at (-0.866,0) ; (D) at (0.866,0) ; (A) – (C) – (B) – (D) – (A) – (B); (A) at (90:1) ; (B) at (210:1) ; (C) at (-30:1) ; (D) at (0,0) ; (D) – (A) – (B) – (D) – (C) – (A); (B) – (C); (A) at (0,0.5) ; (B) at (0,-0.5) ; (C) at (1,-1) ; (D) at (1,0) ; (E) at (1,1) ; (A) – (C) – (B) – (D) – (A) – (E) – (B); Related work ------------ Local certification first appeared under the name of *proof-labeling schemes* in @KormanKP10, inspired by works on self-stabilizing algorithm (see @Dolev2000 for a book on self-stabilization). It has then been generalized under the name of *locally checkable proofs* in @GoosS16, and the field has been very active since these seminal papers. In the following, we will focus on the papers about local certification of graph classes, but we refer to @Feuilloley19 and @FeuilloleyF16 for an introduction and a survey of local certification in general. As said earlier, certification was first mostly about checking that the solution to an algorithmic problem was correct, a typical example being the verification of a spanning tree @KormanKP10. Some graph properties have also been studied, for example symmetry in @GoosS16, or bounded diameter in @Censor-HillelPP20. Very recently, classes that are more central in graph theory have attracted attention. It was first proved in @NaorPY20, as an application of a more general method, that planar graphs can be certified with $O(\log n)$ bits in the more general model of distributed interactive proofs. Then it was proved in @FeuilloleyFMRRT20 that these graphs can actually be certified with $O(\log n)$ bits in the classic model, that is, without interaction. This result was extended to bounded-genus graphs in @FeuilloleyFMRRT21. Later, @EsperetL21 provided a simpler proof of both results via different techniques. It was also proved in @MontealegreRR20 that cographs and distance-hereditary graphs have compact distributed interactive proofs. Still in distributed computing, but outside local certification, the networks with some forbidden structures have attracted a lot of attention recently. A popular topic is the distributed detection of some subgraph $H$, which consists, in the CONGEST (or CONGEST-CLIQUE) model to decide whether the graph contains $H$ as a subgraph or not (see @Censor-HillelFG20 and the references therein). A related task is $H$-freeness testing, which is the similar but easier task consisting in deciding whether the graph is $H$-free or far from being $H$-free (in terms of the number of edges to modify to get a $H$-free graph). This line of work was formalized by @Censor-HillelFS19 after the seminal work of @BrakerskiP11 (see @FraigniaudO19 and the references therein). To our knowledge, no detection/testing algorithm or lower bounds have been designed for $H$-minor-freeness. Finally, we have mentioned in the introduction that certifying that the graph belongs to some given class is important because some algorithms are specially designed to work on some specific classes. For example, there is a large and growing literature on approximation algorithms for *e.g.* planar, bounded-genus, minor-free graphs. We refer to @Feuilloley20 for a bibliography of this area. There are also interesting works for exact problems in the CONGEST model, *e.g.* in planar graphs @GhaffariH16, graphs of bounded treewidth or genus @HaeuplerIZ16 and minor-free graphs @HaeuplerLZ18. In particular the authors of @HaeuplerLZ18 justify the focus on minor-free graphs by the fact that this class allows for significantly better results than general graphs, while being large enough to capture many interesting networks. Very recently, @GhaffariH21 proved general tight results on low-congestion short-cuts (an essential tool for algorithms in the CONGEST model) for graphs excluding dense minor. Organization of the paper ------------------------- The rest of the paper is organized the following way. In Section \[sec:preliminaries\], we state the main definitions and notations, and describe some known certification building blocks. The next three sections describe general tools for graph certification. Namely, Section \[sec:avoiding-congestion\] shows how to avoid having nodes with very large certificates when gluing several certificate assignments together. Section \[sec:composition\] shows how to compose certifications, that is how to combine certification algorithms for several classes in order to certify a larger one. Finally, Section \[sec:connectivity\] focuses on connectivity properties and decompositions. Then in Sections \[sec:diamond-etc\], \[sec:K24\], we illustrate how to use these tools to certify $H$-minor free graphs, for the graphs $H$ summarized in Figure \[fig:our-results-certification\]. With a little more work, this allows us to completely certify in Section \[sec:4vertices\] $H$-minor-free graphs when $H$ has at most 4 vertices (Theorem \[thm:4vertices\]). We then study graphs on 5 vertices in Section \[sec:5vertices\] and solve most of the sparse cases. Finally, in Section \[sec:discussion\], we discuss the obstacles towards obtaining general results about certifying minors, both on the side of upper and lower bounds. Preliminaries {#sec:preliminaries} ============= Graphs and minors ----------------- Let $G=(V,E)$ be a graph. Let $X \subseteq V$. The *subgraph of $G$ induced by $X$* is the graph with vertex set $X$ and edge set $E \cap X^2$. The graph $G \setminus X$ is the subgraph of $G$ induced by $V \setminus X$. A graph $G'$ is a *subgraph* of $G$ if $V' \subseteq V$ and $E' \subseteq E$. For every $v \in V$, $N(v)$ denotes the *neighborhood of $v$* that is the set of vertices adjacent to $v$. The graph $G$ is *$d$-degenerate* if there exists an ordering $v_1,\ldots,v_n$ of the vertices such that, for every $i$, $N(v_i) \cap \{ v_{i+1},\ldots,v_n \}$ has size at most $d$. It refines the notion of maximum degree since any graph of maximum degree $\Delta$ are indeed $\Delta$-degenerate (but the gap between $\Delta$ and the degeneracy can be arbitrarily large). Let $u,v \in V$, a *path* from $u$ to $v$ is a sequence of vertices $v_0=u,v_1,\ldots,v_\ell=v$ such that for every $i \le \ell-1$, $v_iv_{i+1}$ is an edge. It is a *cycle* if $v_\ell v_0$ also exists. A graph $G$ is *connected* if there exists a path from $u$ to $v$ for every pair $u,v \in V$. All along the paper, we only consider connected graphs. Indeed, in certification, the nodes can only communicate with their neighbors, so no node can communicate with nodes of another connected component. A vertex $v$ is a *cut-vertex* if $G \setminus \{ v \}$ is not connected. If $G$ does not contain any cut-vertex, $G$ is *2-(vertex)-connected*. If the removal of any edge does not disconnect the graph, we say that $G$ is *2-edge-connected*. A graph is *$k$-(vertex)-connected* if there does not exist any set $X$ of size $k-1$ such that $G \setminus X$ is not connected. To avoid cumbersome notations, we will simply write $k$-connected for $k$-vertex-connected. A graph $H$ is a *minor of $G$* if $H$ can be obtained from $G$ by deleting vertices, deleting edges and contracting edges. Equivalently, it means that, if $G$ is connected, there exists a partition of $V$ into sets $V_1,\ldots,V_{|H|}$ such that there is (at least) an edge between $V_i$ and $V_j$ if $h_ih_j$ is an edge of $H$. We say that $V_1,\ldots,V_{|H|}$ is a *model of $H$*. The graph $G$ is $H$-minor-free if it does not contain $H$ as a minor. Local computation and certification ----------------------------------- We assume that the graph is equipped with unique identifiers in polynomial range $[1, n^k]$, thus these identifiers can be encoded on $O(\log n)$ bits. Local certification is a mechanism for verifying properties of labeled or unlabeled graphs. In this paper we will use a local certification at distance 1, which is basically the model called *proof-labeling schemes* @KormanKP10. A convenient way to describe a local certification is with a prover and a verifier. The *prover* is an external entity that assigns to every node $v$ a certificate $c(v)$. The *verifier* is a distributed algorithm, in which every node $v$ acts as follows: $v$ collects the identifiers and the certificates of its neighbor and itself, and outputs a decision *accept* or *reject*. A local certification certifies a graph class $\mathcal{C}$ if the following two conditions are verified: 1. For every graph of $\mathcal{C}$, the prover can find a certificate assignment such that the verifier accepts, that is, all nodes output *accept*. 2. For every graph not in $\mathcal{C}$, there is no certificate assignment that makes the verifier accept, that is for every assignment, there is at least one node that rejects. The size of the certificate of $\mathcal{C}$ is the largest size of a certificate assigned to a node of a graph of $\mathcal{C}$. Note that to describe a local certification, the only essential part is the verifier algorithm, the prover is just a way to facilitate the description of a scheme. In this paper, we are going to use a variant of the model above, called *edge certification*, where the certificates can be assigned on both the nodes and the edges. See Subsection \[subsec:edge-certification\]. Known building blocks for graph certification {#subsec:building-blocks} --------------------------------------------- There are few known certification schemes that we are going to use intensively as building blocks in the paper. \[@KormanKP10 [@AfekKY90]\] \[lem:acyclicity\] Acyclicity can be certified in $O(\log n)$ bits. The classic way to certify that the graph is acyclic, is for the prover to choose a root node, and then to give to every node as its certificate its distance to the root. The nodes can simply check that the distances are consistent. The same idea can be used to certify a *spanning tree* of the graph, encoded locally at each node by the pointer to its parent, which is simply the ID of this parent. The scheme is the same, except that the prover, in addition to the distances, gives the ID of the root, and the verification algorithm checks that all nodes have been given the same root-ID, and only takes into account the edges that correspond to pointers (also the root checks that its ID is the root-ID). A spanning tree is a very useful tool to broadcast the *existence of a vertex satisfying a locally checkable property*: simply choose a spanning tree rooted at the special vertex, encode it locally with pointers and certify it. Then the root can check that indeed it has the right property, and all the other vertices know that such a vertex exists. Finally, with the same ideas, one can easily deduce $O(\log n)$ certification for paths. We just add to the acyclicity scheme the verification that the degree of every node is at most 2. Note that cycles do not need certificates to be verified: every node just checks that it has degree exactly 2. Let us now define a graph class that will appear in several decompositions. A *path-outerplanar* graph is a graph that admits a Hamiltonian path $P$ that can be drawn on a horizontal line, such that all the edges that do not belong to $P$ can be drawn above that line without crossings. The edges are said to be *nested*. We are going to use the following result as a black box. \[@FeuilloleyFMRRT20\]\[lem:path-outerplanar\] Path-outerplanar graphs can be certified with $O(\log n)$-bit certificates. The following classic result will also be useful at some point of the paper. \[@KormanKP10\] \[lem:universal\] Every graph class can be certified with $O(n^2)$ bits. The idea of the scheme is that the prover gives to every node $v$ the map of the graph, *e.g.* as an adjacency matrix, along with the position of $v$ in this map. Then every node can check that it has been given the same map as its neighbors, and that the map is consistent with its neighborhood in the network. Avoiding certificate congestion {#sec:avoiding-congestion} =============================== One can obtain many structured graph classes like minor free graphs with "gluing" operations, for instance by identifying vertices of two graphs of the class. If we have a certification for both graphs, we would like to simply take both certificate assignments to certify the new graph. However, for the vertex on which the two graphs are glued, the size of the certificate might have doubled. While it is not a problem for bounded degree graphs, it can become problematic if many gluing operations occur around the same vertex, since this vertex would get an additional certificate from each operation. In this section, we present two ways to tackle these issues, that will be used in the forthcoming sections. The first one consists in shifting the certification on edges instead of vertices, which helps in the sense that when gluing on vertices the edge certificate can remain unchanged. As we will see, the edge setting is equivalent to the usual vertex certification for nice enough classes. The second option uses that one can (almost) freely assume that a given vertex has an empty label in a correct certification. Edge certification and degeneracy {#subsec:edge-certification} --------------------------------- Transforming a node certification into an edge certification can always be done without additional asymptotic costs: just copy on every edge the certificate of the two endpoints, and adapt the verification algorithm accordingly. Transforming an edge certification into a node certification is also always possible, by giving a copy of the edge label to each of its endpoint. But this transformation can drastically increase the certificate size: if an edge certification uses $\Omega(f(n))$-bit labels, the associated node certification might use $\Omega(n \cdot f(n))$-bit if the maximum degree of the graph is linear. The following theorem ensures that in degenerate graph classes there is a more efficient transformation that permits to drastically reduce the size of the certificate. \[@FeuilloleyFMRRT21\]\[thm:degeneracy\] Consider an edge certification of a graph class $\mathcal{C}$ where the edges are labeled with $f(n)$-bit certificates. If $\mathcal{C}$ is $d$-degenerate, then there exists a (node) certification with $d\cdot f(n)$-bit certificates. Note that $H$-minor free graphs have degeneracy $O(h \sqrt{\log h})$ where $h=|V(H)|$ @kostochka1982minimum [@thomason84]. Therefore, we can freely put labels on edges when certifying classes defined by forbidden minors. Certification with one empty label ---------------------------------- In this part, our goal is to erase the certificate of a node. To this end, we first consider certification of spanning trees and strengthen both Lemma \[lem:acyclicity\] and the discussion that followed in Subsection \[subsec:building-blocks\]. We then extend this intermediate step to every graph class in Lemma \[lem:pointed\]. \[lem:ST-with-no-root-label\] Let $T$ be a spanning tree of $G$. There exists a certification of a $T$ that does not assign a label to the root and whose size of all the other labels is the usual size of a label certificate for trees. On *yes*-instances, the prover assigns the labels as in the classic scheme, and removes the label of the root. Then the verification proceeds like in the classic scheme except for a node that has no label or a node that has a neighbor with no label. If two adjacent nodes have been given an empty label, then they reject. If a node with no label sees that two of its neighbors have been given different root-ID, then it rejects. Otherwise, every node simulates the computation where the node with empty label has been given distance 0, and the same root-ID as its neighbors. Because of the previous checks, the labels used in the simulation are consistent, and on correct instance are the same as the one used in the classic certification. Thus, the correctness follows from the correctness of the classic scheme. A *pointed graph* is a graph with one selected node. Given a class, one can build its pointed version by taking for each graph all the pointed versions of it. \[lem:pointed\] Consider a class $\mathcal{C}$ that can be certified with certificates of size $f(n)$. One can certify the pointed class of $\mathcal{C}$ with $O(f(n)+\log n)$ bits, without having to put certificates on the selected node. First, to certify that exactly one node is pointed, we can simply find a spanning tree rooted on the pointed vertex and assign to each node the spanning tree certification of Lemma \[lem:ST-with-no-root-label\] which uses $O(\log n)$ bits. For the rest of the certification, on a *yes*-instance, the prover first assigns the certificates following the original certification. Then it removes the certificate of the selected node and appends copies of it to the certificates of its neighbors. Every node $v$ runs the following verification. If $v$ is not the selected node, nor one of its neighbors, then it does the same verification as before. If $v$ is the selected node, it checks that its neighbors have been given the same label as "label of the selected node", and then takes this label as its own, and runs the previous verification algorithm. If $v$ is a neighbor of the selected node, it runs the same verification algorithm as before, but simulating that the selected node has been given the certificate that was appended to its own certificate. All nodes are simulating the computation in the graph where the selected node would have been given its certificates, thus the correctness of this new certification follows from the correctness of the original certification. Observe that the previous results can be easily iterated: one can always remove the labels of $k$ nodes (as long as they are pairwise non-adjacent) to the cost of a factor $k$ in the size of the certificates. Therefore, the result extends to the case of $k$-independent pointed classes (i.e. where an independent set of size at most $k$ is selected instead of only one vertex). \[coro:pointed\] Consider a class that can be certified with certificates of size $f(n)$. One can certify the $k$-independent pointed class with $O(kf(n)+k\log n)$ bits, without having to put certificates on the selected nodes. Moreover, with more constraints on the structure of the set of pointed vertices (for instance if they are all at distance at least 3), one could even obtain certificate of size $O(f(n)+k\log n)$ (since every node receives the certificate of at most one selected node). Compositions of certifications {#sec:composition} ============================== In this section, we show how to combine certification algorithms for several classes to certify larger ones, and we illustrate this idea on two constructions. The first one considers classes defined by the existence of some subgraph: we settle the intuition stating that it is often easier to test the existence of a structure rather than its absence, since we can pinpoint which nodes/edges lie in the structure. The second construction mimics a natural operation on graphs, consisting in replacing some vertex/edge by another graph. This operation occurs quite often in the literature: many classes, especially the ones defined by forbidden minors, get a characterization using this operation. Subgraphs --------- \[prop:subgraph\] Let $\mathcal{C}$ be a graph class that can be certified with $f(n)$-bit labels. Let $\mathcal{C}'$ be the class of the graphs that contain a graph of $\mathcal{C}$ as subgraph. Then $\mathcal{C}'$ can be certified with certificates of size $O(f(n)+\log n)$ on the nodes and $O(1)$ on the edges. On a *yes*-instance $G$, the prover assigns the certificates on nodes and edges in the following way. First, it chooses a subgraph $H$ that belongs to $\mathcal{C}$ and assigns the certificates that certify that $H$ is in $\mathcal{C}$, as if the rest of the graph did not exist. This takes at most $f(n)$ bits. Second to every node and edge that belongs to $H$, the prover assigns a special label. Third, the prover describes and certifies a spanning tree pointing to a node that has the special label. The verification algorithm is the following. The nodes that have the special label, run the verification algorithm for $\mathcal{C}$, taking into account only the nodes and edges that have the special label. The nodes also check the spanning tree structure, and the root of the tree checks that it does have the special label. Because of the spanning tree, there must exist a node with the special label, thus there are nodes that run the verification algorithm for $\mathcal{C}$, and if they succeed it means that a graph of $\mathcal{C}$ appears as a subgraph in the graph $G$. The edge certificates in Proposition \[prop:subgraph\] can be inconvenient if we want a classic certification (without edge certificates) and if the graph is not assumed to be degenerate, which prevents us from using Theorem \[thm:degeneracy\]. However, observe that we give non-empty certificates only to the edges of the subgraph, hence we can obtain a vertex-certification when the class $\mathcal{C}$ is degenerate. \[cor:subgraph\_deg\] Let $\mathcal{C}$ be a $d$-degenerate graph class that can be certified with $f(n)$-bit labels. Let $\mathcal{C}'$ be the class of the graphs that contain a graph of $\mathcal{C}$ as subgraph. Then $\mathcal{C}'$ can be certified with certificates of size $O(f(n)+d\log n)$ on the nodes. Observe also that when considering induced subgraphs, we only have to specify which vertices are special, hence we do not need edge certificates either. Note that, since we do not need to label edges, we do not need the class $\mathcal{C}$ to be degenerate. \[cor:subgraph\_induced\] Let $\mathcal{C}$ be a graph class that can be certified with $f(n)$-bit labels. Let $\mathcal{C}'$ be the class of the graphs that contain a graph of $\mathcal{C}$ as an induced subgraph. Then $\mathcal{C}'$ can be certified with certificates of size $O(f(n)+\log n)$ on the nodes. Expansions ---------- Two common operations in characterizations of graph classes are what we call node and edge expansions. Consider two graph classes $\mathcal{C}_1$ and $\mathcal{C}_2$. - The *node expansion of $\mathcal{C}_1$ by $\mathcal{C}_2$* is the class of graphs obtained by the following operation. Take a graph $G$ in $\mathcal{C}_1$ and replace every node $v$ by a graph $H(v)$ in $\mathcal{C}_2$, in such a way that for every edge $uv\in E(G)$, there is (at least) one edge between $H(u)$ and $H(v)$ in $G$ (and no such edge if $uv\notin E(G)$). - The *edge expansion of $\mathcal{C}_1$ by $\mathcal{C}_2$* is the class of graphs obtained by the following operation. Take a graph $G$ in $\mathcal{C}_1$ and replace every edge $uv$ by a graph $H(u,v)$ from $\mathcal{C}_2$, in such a way that the nodes of the original graph that are contained in $H(u,v)$ are exactly $u$ and $v$. We would like to have results of the form: if $\mathcal{C}_1$ and $\mathcal{C}_2$ can be certified with $f(n)$ and $g(n)$-bit labels respectively, then the expansion can be certified with $O(f(n)+g(n))$-bit labels. While the natural approach (almost) works for edge-expansion, it does not give such a result for node-expansion. However, we can actually make it work with a bound that takes into account the maximum degree of the expanded graph. \[prop:node-expansion\] Consider two graph classes $\mathcal{C}_1$ and $\mathcal{C}_2$ that can be certified with $f(n)$-bit and $g(n)$-bit labels respectively, where all the graphs of $\mathcal{C}_1$ has maximum degree $\Delta$. Then the node-expansion of $\mathcal{C}_1$ by $\mathcal{C}_2$ can be certified with $O(\Delta \cdot f(n)+g(n)+\Delta\log n)$-bit certificates. Consider a graph $G\in \mathcal{C}_1$ on $\ell$ nodes $v_1,\ldots,v_\ell$ of maximum degree $\Delta$, and let $H_1,\ldots,H_\ell$ be graphs of $\mathcal{C}_2$. We consider the node expansion of $G$ where every $v_i$ is replaced by $H_i$. On a *yes*-instance, the prover assigns the certificates the following way. First it assigns to every node the index $i$ corresponding to the graph $H_i$ it belongs to and the certification of the fact that $H_i$ belongs to $\mathcal{C}_2$ (without taking into accounts the other nodes and edges). This takes at most $g(n)+\log n$ bits per node. Second, the prover gives to each vertex of $H_i$ the original certificate of $v_i$ that $G$ belongs to $\mathcal{C}_1$ as well as the original certificate of all the vertices in $N(v_i)$ in $G$ together with their names, which takes $O(\Delta f(n))$ bits. Finally, for every $v_j\in N(v_i)$, the prover chooses a vertex $w_j$ in $H_i$ adjacent to a vertex in $H_j$, and certifies a spanning tree of $H_i$ rooted at $w_j$. This takes $O(\Delta\log n)$ bits. The verification algorithm is the following. Every node (labeled as) in $H_i$ checks that the number of trees corresponds to the degree of $v_i$ in $G$. Every node checks the correctness of the different trees. Moreover, every root $v$ of a spanning tree in $H_i$ checks that it has a neighbor in the corresponding $H_j$. All the nodes of $H_i$ check that their neighbors are in $H_i$ or in some $H_j$ with $v_j$ incident to $v_i$ in $G$. Every node of each $H_i$ runs the verification algorithm to check that $H_i$ does belong to $\mathcal{C}_2$. Finally, every node of $H_i$ simulates the verification of the original node $v_i$, which is possible since every vertex of $H_i$ receives the certificate of $v_i$ and all its neighbors in $G$. And every vertex $w_i \in H_i$ incident to $w_j \in H_j$ checks that $v_j\in N_G(v_i)$ and that the certificate of $w_j$ indeed contains the certificates of $v_i$ and $v_j$ given for $G$. \[prop:edge-expansion\] Consider two graph classes $\mathcal{C}_1$ and $\mathcal{C}_2$ that can be certified with $f(n)$-bit and $g(n)$-bit labels respectively. Then the edge-expansion of $\mathcal{C}_1$ by $\mathcal{C}_2$ can be certified with $O(f(n)+g(n)+\log n)$-bit certificates on the edges. We use a similar reasoning as for the proof of Proposition \[prop:node-expansion\], except that we first transform the node certifications of $\mathcal{C}_1$ and $\mathcal{C}_2$ into edge certifications (by putting the label of a node on all the edges incident with it). Consider a graph $G\in \mathcal{C}_1$. We consider the edge expansion of $G$ where every $uv$ is replaced by $H(u,v)$. Each edge $e$ from $H(u,v)$ receives the labels of $u$ and $v$, the certificate of $uv$ in $G$ for $\mathcal{C}_1$, and the certificate of $e$ in $H(u,v)$ for $\mathcal{C}_2$. Therefore, the certificates have size $O(f(n)+g(n)+\log n)$. Now each vertex can check that all the edges labeled in some $H(u,v)$ share the same certificate for $uv$. There are two kinds of nodes: some where all incident edges are labeled as in the same $H(u,v)$, and the others (the original vertices of $G$). All of them run the verification algorithm for $\mathcal{C}_2$ by considering each group of incident edges labeled as in the same $H(u,v)$. The latter also recover the certificates of their neighbors in $G$ from the edge labeling, and run the verification algorithm for $\mathcal{C}_1$. Before giving deeper applications of these results in future sections, let us illustrate a simple application of these techniques to prove the following result, mentioned in previous papers without formal proofs @FeuilloleyFMRRT20 [@FeuilloleyFMRRT21]. Given a graph $H$, one can certify that a graph has $H$ as a minor in $O(\log n)$ bits. As we already observed, a graph $G$ has $H$ as minor if and only if $V(G)$ can be partitioned into $|H|$ connected sets such that there is an edge between $V_i$ and $V_j$ when the corresponding vertices in $H$ are connected. Free to delete edges, we can assume that each $V_i$ is actually a spanning tree and there is a unique edge from $V_i$ to $V_j$ if and only if the corresponding vertices are connected in $H$. In other words, $G$ has a subgraph that is a node expansion of $H$ by trees. Moreover, we can choose such a subgraph with degree at most $|H|-1=O(1)$ since $H$ is fixed. Let us start from a certification of $H$ and build a certification of $G$. The structure of $H$ can be certified in a brute-force way, by providing to every node the complete map of the graph which takes constant space (since $H$ is fixed). Then, since trees can be certified in $O(\log n)$ bits, thanks to Proposition \[prop:node-expansion\], any node-expansion of $H$ by trees can be certified with $O(\log n)$ certificates. We finally get a node certification with certificates of size $O(\log n)$ using Corollary \[cor:subgraph\_deg\]. Connectivity and connectivity decompositions {#sec:connectivity} ============================================ An *ear decomposition* is a way to build a graph by iteratively adding paths, the so-called *ears*. Ear decompositions are central tools for decades in structural graph theory and are used in many decomposition or algorithmic results. There exists various variants of this process, that characterize different classes and properties. For certification, these decompositions happen to be easier to manipulate than some other types of characterizations since they are based on iterative construction of the graph, and use paths, which are easy to certify. These paths are convenient since we can "propagate" some quantity of information on them as long as every vertex belongs to a bounded number of paths. In this section, we remind several such decompositions, and use them to certify various connectivity properties and decompositions. Connectivity properties ----------------------- Let us start with 2-connectivity. A graph $G$ has an *open ear decomposition* if $G$ can be built, by starting from a single edge, and iteratively applying the following process: take two different nodes of the current graph and link them by a path whose internal nodes are new nodes of the graph. Note that this path can be reduced to a single edge, and then there is no new node. Let an *inner node* of an ear be a vertex that is created with this ear, and let a *long ear* be an ear with at least one inner node. \[@Whitney32 (reformulated)\] A graph is 2-connected if and only if it has an open ear decomposition. We use this characterization to certify 2-connectivity. \[lem:2-connected-graphs\] 2-connected graphs can be certified with $O(\log n)$ bits. First observe that one can obtain a long-ear decomposition from an ear decomposition (and vice versa) by removing/adding short ears, i.e. edges. Therefore, having an open ear decomposition is equivalent to having a subgraph with an open long-ear decomposition. Note that if a graph $G$ has an open long-ear decomposition, then it is $2$-degenerate. Indeed, the vertices of the last added long-ear have degree two and their removal is still a graph with an open long-ear decomposition. So in order to get the conclusion, Corollary \[cor:subgraph\_deg\] ensures that we only have to certify open long-ear decomposition with $O(\log n)$ bits per vertex. The certification works as follows. First the prover gives to every node the identifiers of the very first edge, and describes and certifies a spanning tree pointing to one of the endpoints of this edge. The nodes of this edge are given an *index* 0. Second, the prover gives to every node the information related to the step when it has been added, and only about this step. That is, the prover gives the *index* of the addition (that is the number of the ear in which the vertex is created), along with two oriented paths spanning the path and pointing to the two extremities of the ear. By Corollary \[coro:pointed\], these paths can be certified without certificates on the extremities of the paths. Every node checks the correctness of the spanning tree pointing to the first edge, and the fact that only these nodes have index 0. Then, every node also checks that the spanning paths it has been given are correct, that is: (1) the distances and root-ID are consistent (2) all nodes have the same index, and that (3) the declared endpoints are different. Also, the two nodes that are adjacent to the endpoints of the paths check that the endpoints have a smaller index than their own. Let us now prove the correctness of the certification. Because of the spanning tree, the original edge exists, is unique, and is the only set of nodes with index 0. Because of the certified paths spanning the ears, one can also recover the path structure and the fact that a path is added after its endpoints. Note that in an instance where all nodes accept, there might be two different paths with the same index $i$, but this is not a problem: the only important feature is the precedence order. With similar construction we can certify the edge connectivity instead of the vertex connectivity. \[coro:2-edge-connected\] 2-edge-connected graphs can be certified with $O(\log n)$ bits. Robbins proved in @Robbins39 that a graph $G$ is 2-edge connected if and only if $G$ has an ear decomposition. An ear decomposition is the same as an open ear decomposition, except that it starts from a cycle and that the two endpoints of an ear do not need to be different. The proof above can thus be adapted to this class. The only difference is that vertices with index $0$ form a cycle (which can be certified). Then during the verification procedure we simply do not have to check that the extremities of the path of the ear decomposition are distinct, in other words we do not have to check (3). A more refined type of ear decomposition characterizes the 3-vertex-connected graphs. \[@Schmidt16 [@Mondshein71; @CheriyanM88]\] Let $ru$ be an edge of the graph $G$. A *Mondshein sequence avoiding $ru$* is an open ear decomposition of $G$ such that: 1. $r$ is in the first ear. 2. the ear that creates node $u$ is the last long ear, $u$ is its only inner vertex, and it does not contain $ru$. 3. the ear decomposition is non-separating, that is, for every long ear except the last one, every inner node has a neighbor that is created in a later ear. \[@CheriyanM88\] Let $ru$ be an edge of $G$. The graph $G$ is 3-vertex-connected if and only if it has a Mondshein sequence avoiding $ru$. \[coro:3-connected\] 3-connected graphs can be certified with $O(\log n)$ on vertices and $O(1)$ on edges. On *yes*-instances the prover chooses an arbitrary edge $ru$ and certifies the ear decomposition as in Lemma \[lem:2-connected-graphs\]. The prover also add a spanning tree pointing to the edge $ru$ and gives to every index of the last long ear created. These new pieces of information allow the nodes to check that the ear decomposition is a Mondshein sequence. Block-cut tree -------------- Now that we can certify connectivity properties, we introduce a way to certify decomposition of graphs into parts of higher connectivity. Let us start with a few definitions. A *2-connected component* of a graph $G$ is a connected subgraph $H$ maximal by inclusion such that the removal of one node does not disconnect $H$. Observe that a 2-connected component can be reduced to an edge in the case of a bridge, i.e. an edge whose removal disconnects the graph. For every pair $C,C'$ of 2-connected components, one can prove that their intersection has size at most one. So we can define an auxiliary graph from $G$ where every node corresponds to a 2-connected component and there is an edge between two components if and only if they intersect on exactly one node. One can prove that this graph is a tree and is called the *block-cut tree*. Let $T$ be a block-cut tree of $G$, and $D$ a maximal 2-connected component chosen to be the root of this tree. (Note that if $G$ is $2$-connected then the graph is reduced to this component). Let $C$ be a component that is not the root of the tree. The *connecting node* of a component $C$ is the node lying both in $C$ and in its parent component. The *interior* of $C$ is the set of nodes of $C$ minus the connecting node of $C$. Note that the interior of a component is always non-empty. This section is devoted to proving the following result and apply it for certification: \[thm:2-connected-to-general\] For any 2-connected graph $H$, if the 2-connected $H$-minor-free graphs can be certified with $f(n)$ bits, then the $H$-minor-free graphs can be certified with $O(f(n)+\log n)$ bits. \[Proof of Theorem \[thm:2-connected-to-general\]\] Since $H$ is 2-connected, a graph $G$ is $H$-minor-free if and only if each of its 2-connected components is. This is the property we certify. On a *yes*-instance, the prover will assign the certificates the following way. It first computes the block-cut tree and root it on some node $C$. It then does the following: 1. For each 2-connected component, the prover chooses a node from the interior of the component to be the *leader* of this component. Every node of the interior of a component $C$ is given the identifier of the leader of $C$ as well as a spanning tree of $C$ pointing towards it. Since the component is $2$-connected, the component minus the leader of the component is connected and such a tree exists. 2. Every node is given a label stating whether it is a connecting node or not. 3. Every node is given the identifier of the connecting node of its component closest from the root in the block-cut tree (called the *component* of the node), as well as a spanning tree pointing to it, using the certification of Lemma \[lem:ST-with-no-root-label\] that uses an empty certificate on the root. 4. In order to check acyclicity of the block-cut tree, every node is given the distance of its component to the root-component (in terms of number of components). 5. The prover certifies the $2$-connectivity of each component using the certification of Lemma \[lem:2-connected-graphs\] and the fact that it is $H$-minor free using the certification with $f(n)$ bits of the theorem. By Lemma \[lem:pointed\] this can be done by only assigning labels to the interior nodes of the component. Before we move on to the verification and the correctness of the scheme, note that every node is given a certificate of size $O(f(n)+\log n)$. Indeed, each piece of information we have given to the node is of size $O(\log n)$ or $f(n)$, and we have given a constant number of those to every node. In particular, a connecting node in the interior of a component $C$, received only labels that are related $C$, and not labels related to other components it belongs to (since we consider pointed components). Now, every node does the following verification. Every node checks that the spanning tree pointing to the leader is correct. If this step succeeds, we have a partition of the nodes in components. Every node also checks the correctness of the spanning tree pointing to the connecting node. Every node $v$ checks that, if it has an edge to a connecting node $w$ with a different leader, then $w$ is the connecting node of its own component. Every connecting node $v$ checks that it is connected to a single node in its parent component and that it is the claimed neighbor in that component. If this step succeeds, we have a decomposition into components linked by connecting nodes. The consistency of the component distances are also checked by the nodes: this distance should be decremented at each connecting node, and only there. This ensures the acyclicity of the component structure. Finally, every node checks that the $2$-connectivity and the $H$-minor-freeness of its component. Globally this verification ensures that the graph is $H$-minor-free. Application to $C_4$, Diamond, $K_4$ and $K_{2,3}$ minor-free graphs {#sec:diamond-etc} ==================================================================== This section is devoted to the certification of $C_4$-minor-free, diamond-minor-free graphs, $K_4$-minor-free graphs and $K_{2,3}$-minor-free graphs. All the proofs will follow the same structure: prove that the 2-connected components, which are more structured, can be certified with small labels, and then use Theorem \[thm:2-connected-to-general\] to conclude for the general case. Before going to this proof let us describe how to certify how to certify *series-parallel graphs*, which in addition to be interesting network topologies @FlocchiniL03, are closely related to $K_4$-minor-free graphs. A *(2-terminal) series-parallel graph* is a graph with two labeled vertices called the *source* and the *sink* that can be built recursively as follows. A single edge is a series-parallel graph where one endpoint is the source and the other is the sink. Let $G_1,G_2$ be two series-parallel graphs. The *series* of $G_1$ and $G_2$ which consists in identifying the sink of $G_1$ and the source of $G_2$ is a series-parallel graph. The *parallel* of $G_1$ and $G_2$, which consists in merging the sources of $G_1$ and $G_2$ together and merging the sinks of $G_1$ and $G_2$ together, is a series parallel graph. A *nested ear decomposition* is an open ear decomposition that starts from a path, with two properties: (1) both ends of an ear have to be connected to the same ear, and (2) for every ear, the ears that are plugged onto it are nested. Eppstein proved the
{'source': 'arXiv_out/2108'}