Nicolas Bousquet
email: nicolas.bousquet@univ-lyon1.fr

Linda Cook
email: lindacook@ibs.re.kr

Sébastien Zeitoun
email: sebastien.zeitoun@univ-lyon1.fr.

Local certification of forbidden subgraphs

Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph detection from the perspective of local certification. Remember that a local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. Our main question is: For a given graph 𝐻 , what is the minimum certificate size that allows checking that the network does not contain 𝐻 as a (possibly induced) subgraph? We show a variety of lower and upper bounds, uncovering an interesting interplay between the optimal certificate size, the size of the forbidden subgraph, and the locality of the verification. Along the way we introduce several new technical tools, in particular what we call the layered map, which is not specific to forbidden subgraphs and that we expect to be useful for certifying many other properties.

INTRODUCTION

Context

Finding some given small structures in a graph, triangles for example, has become a major theme in the area of distributed graph algorithms. A lot of effort has been put recently in understanding various versions of this problem (detection, listing, counting, and testing) in several congested models, especially Congest and Congested cliqe. We refer to the recent survey by Censor-Hillel [START_REF] Censor-Hillel | Distributed Subgraph Finding: Progress and Challenges[END_REF] for an introduction to the topic and a full bibliography. This fundamental problem turned out to be very challenging and has been an incubator for new techniques, such as the expander decompositions [START_REF] Chang | Distributed Triangle Detection via Expander Decomposition[END_REF] (that has later been used in other contexts, for example for derandomizing minimum spanning tree construction [START_REF] Chang | Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization[END_REF]).

Substructure detection has also become an important research topic in the more specific field of local certification. In local certification, one is interested in how much memory it takes to store a locally checkable certification of some given property. More precisely, for a given property, a local certification consists in a local algorithm taking as input a neighborhood around each node, along with labels assigned to nodes, called certificates, and outputting a binary decision, accept or reject. A certification scheme is correct if the following holds: there exists an assignment of certificates such that the local algorithm accepts at every node, if and only if, the property is satisfied in the network. Actually, the notion originates from self-stabilization [START_REF] Korman | Proof labeling schemes[END_REF], where one certifies the output of an algorithm, but in this paper we will focus on properties of the network itself. We refer to [START_REF] Feuilloley | Introduction to local certification[END_REF] for an introduction to local certification. (Formal definitions will be given later.)

The classic measure of quality of a local certification is the size of the certificate, as a function of 𝑛, the size of the graph. For example, certifying that a graph is acyclic can be done with certificates of size 𝑂 (log 𝑛), and this is optimal. One often separates graph properties into two broad categories: the ones that have a compact certification, that is of (poly)logarithmic size, and the ones that do not, and typically need linear or even quadratic size 1 . This distinction can be seen as a local versus global dichotomy, if one considers the certificates to be the amount of global information needed to locally decide a property. Understanding what are the properties that fall in each of these regimes has been a major direction in the area in recent years, in particular with meta-theorems partially capturing the compact properties [START_REF] Feuilloley | What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs[END_REF][START_REF] Fraigniaud | Distributed Certification for Classes of Dense Graphs[END_REF][START_REF] Fraigniaud | A Meta-Theorem for Distributed Certification[END_REF].

When it comes to local certification of network substructures, the positive case, that is certifying that a given substructure exists in the network, is often easy. Indeed, one can often simply put the names of the vertices involved in the certificates of all vertices, and use a locally-encoded spanning tree to point to a node of the structure. The real challenge is to certify that some structure is absent from the network, which is intuitively a much more global property. In that direction, the community has been focusing on one type of substructures, namely graph minors. Remember that a graph 𝐻 is a minor of a graph 𝐺 is it can be obtained from 𝐺 by edge and vertex removals, as well as edge contractions. The following is one of the key questions of the area.

Conjecture 1.1 (Excluded-minor certification conjecture). For every graph 𝐻 , certifying that a graph is 𝐻 -minor-free can be done with certificates of size 𝑂 𝐻 (log 𝑛).

The conjecture has been proved for planar graphs [START_REF] Feuilloley | Compact Distributed Certification of Planar Graphs[END_REF], bounded-genus [START_REF] Esperet | Local certification of graphs on surfaces[END_REF][START_REF] Feuilloley | Local certification of graphs with bounded genus[END_REF], small excluded minors [START_REF] Bousquet | Local Certification of Graph Decompositions and Applications to Minor-Free Classes[END_REF], path and cycle minors [START_REF] Feuilloley | What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs[END_REF], and planar minors (with polylogarithmic certificates) [START_REF] Fraigniaud | A Meta-Theorem for Distributed Certification[END_REF]. A relaxed version has also been proved for every 𝐻 [START_REF] Esperet | Testability and Local Certification of Monotone Properties in Minor-Closed Classes[END_REF], but the full conjecture is still widely open.

In this paper, our focus is not minors but another type of substructure, namely subgraphs, which are actually more popular in distributed computing, as discussed above. The general question we want to answer is the following. Question 1.2. What is the optimal label size for certifying that the network does not contain a fixed graph 𝐻 as a non-induced or an induced subgraph?

Remember that a graph 𝐻 is a (non-induced) subgraph of 𝐺 if it can be obtained from 𝐺 by removing vertices and edges, and an induced subgraph of 𝐺 if it can be obtained from 𝐺 by removing only vertices (and the edges adjacent to these removed vertices). 2,3 Subgraphs, which are very localized in the graph, might look easier to manage than minors, which can span a large part of the graph (because of the contraction operation). And indeed, if one allows the local verification algorithm to look at large enough (constant) distance, every node can see whether the forbidden subgraph appears or not in its neighborhood. But if we do not allow this, then the problem seems to become more challenging than for minors. Intuitively, since minors can appear in many ways in a graph, forbidding one constrains the graph structure a lot, and one can use this structure for certification. For example, forbidding a triangle as minor implies that the graph is a tree, while forbidding a triangle as induced subgraph still leaves a very complex graph class.

Discussion of previous work and refinement of the question

As mentioned earlier, there is a large literature on subgraphs detection in various distributed models. In general, results in these models are difficult to adapt to local certification. Indeed, on the one hand, the non-constructive aspect of certificates makes the latter a stronger model, but on the other hand, local certification is a broadcast-type model, in the sense that all neighbors see the same information from a specific node, which implies that comparisons with unicast models such as Congest are rarely useful. 4The only model that is clearly useful for us is Broadcast Congest where, at each round, each node sends the same 𝑂 (log 𝑛)-bit message to all its neighbors. Suppose that there is an upper bound of 𝑓 (𝑛) rounds in this model to detect some subgraph (where detection means that if the graph contains one or several copies of the subgraph, then at least one node will detect at least one copy). Then we can derive an upper bound of 𝑂 (𝑓 (𝑛) log 𝑛) for certification, by encoding in the certificate of each node all the messages that it sends during the run of the algorithm. Indeed, given this information, every node can check that the run is correct, and a node rejects this certification in the end, if and only if, the output of the original algorithm is a detection.

A nice result proved in [START_REF] Even | Three Notes on Distributed Property Testing[END_REF][START_REF] Janne | Deterministic Subgraph Detection in Broadcast CONGEST[END_REF] is that any tree on 𝑘 vertices can be detected in 𝑂 (𝑘2 𝑘 ) rounds of the Broadcast Congest model. From this result and the reasoning above, we derive the following theorem.

Theorem 1.3 (Derived from [START_REF] Even | Three Notes on Distributed Property Testing[END_REF][START_REF] Janne | Deterministic Subgraph Detection in Broadcast CONGEST[END_REF]). For any tree 𝑇 , certifying that a graph contains 𝑇 as a (not necessarily induced) subgraph can be done with certificates of size 𝑂 (log 𝑛) bits.

Actually, one can also derive this result from the meta-theorem of [START_REF] Feuilloley | What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs[END_REF] (see Corollary 2.7, noting that forbidding a path of length 𝑡 as a minor is equivalent to forbidding it as a (non-induced) subgraph). From the same paper, one can adapt a matching lower bound (see Section 7 in [START_REF] Feuilloley | What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs[END_REF]).

Given that the techniques to obtain Theorem 1.3 are very specific to non-induced subgraphs (roughly, a lot of information about non-edges is lost in the kind of compression that allows to store so little information), a first concrete question is the following. Question 1.4. What is the optimal certificate size for induced trees?

For this question, the only non-trivial case known in the literature is for 𝑃 4 -free graphs 5 , which can be certified with 𝑂 (log 𝑛) bits [START_REF] Fraigniaud | Distributed Certification for Classes of Dense Graphs[END_REF]. This proof is not really helpful to understand the general case, since it heavily uses the fact that 𝑃 4 -free graphs are the same as cographs, a graph class whose well-understood structure can be efficiently utilized for certification.

For lower bounds, results in BROADCAST CONGEST cannot be adapted directly, but the techniques can sometimes be borrowed. This is the case for the following theorem for cliques. (Note that, for cliques, induced and non-induced subgraphs are equivalent.) Theorem 1.5 (Derived from Proposition 5 in [START_REF] Crescenzi | Trade-Offs in Distributed Interactive Proofs[END_REF], see also [START_REF] Drucker | On the power of the congested clique model[END_REF]). For constant 𝑘, certifying 𝐾 𝑘 -free graphs requires certificates of size Ω(𝑛/𝑒 𝑂 (log √ 𝑛) ) bits.

Actually, [START_REF] Crescenzi | Trade-Offs in Distributed Interactive Proofs[END_REF] only mentions the result for triangles, but it is easy to generalize it to cliques. Indeed, if there would exist a more compact certification of larger cliques, one could use it to certify triangles, by simulating 𝑘 -3 virtual nodes adjacent to every node of the graph, i.e. by giving their certificate in a 𝐾 𝑘 -freeness certification to every node of the original graph.

At that point, one might simply conclude that being 𝐾 𝑘 -free is a global property, since it needs polynomial size proof, and move on to the next problem. We claim that understanding where is the right complexity on the spectrum between Θ(𝑛) and Θ(𝑛 2 ) (or more precisely Θ(𝑚), where 𝑚 is the number of edges) is actually an important question. A useful analogy here is with the CONGEST model, where algorithm running in 𝑂 (𝑛) rounds are considered efficient (and are often optimal), whereas larger complexities, especially Θ(𝑛 2 ), means that the problem is hard. The same intuition is true for local certification: using 𝑜 (𝑛 2 ) bits means that (in dense graphs) we can avoid transferring information about all the edges, and having (quasi-)linear certificates means that one can store only a small piece of information per node of the graph. We will see later that this approach is also fruitful technically, since it forces one to design nice new tools and data structures.

We phrase this point of view into a question.

Question 1.6. For the (induced) subgraphs that require polynomial certificate size, what are the right polynomials? Are they (quasi)-linear in the number of vertices, or in the number of edges? Or in between?

As a side remark, note that when forbidding non necessarily induced subgraphs or minors, and taking only 𝑛 as a parameter, one can use the fact that the number of edges is bounded away from 𝑛 2 , but this is not true for induced subgraphs (for example a clique does not contain any induced copy of 𝑃 𝑘 for 𝑘 > 2).

For the case of cliques, we can actually almost match the lower bound of Theorem 1.5.

Theorem 1.7. Certifying that a graph does not contain a given constant-size clique as a subgraph can be done with 𝑂 (𝑛 log 𝑛) bits.

To establish this theorem, we give as a certificate to each node the list of the identifiers of its neighbors. Of course, this is useless for the node itself, since it knows this information, but it allows its neighbors to have knowledge at distance 2, which is enough for detecting cliques. 6 Note that this techniques is not restricted to cliques: it applies to any setting where the forbidden subgraph would be detected automatically if we could increment the radius by 1.

After paths and cliques, a natural direction is to target cycles and some specific small subgraphs (e.g. diamonds). Here, we know from personal communication [START_REF] Chaniotis | [END_REF] that some cases have been solved: non-induced cycles require Ω(𝑛) bits, and the technique based on triangles [START_REF] Crescenzi | Trade-Offs in Distributed Interactive Proofs[END_REF][START_REF] Drucker | On the power of the congested clique model[END_REF] allows proving subpolynomial lower bounds for various small graphs. We take another direction, that opens new perspectives and, as side results, we will also obtain answers to some of these questions.

As mentioned earlier, certifying that a subgraph is absent from a graph is trivial if the nodes can see far enough in the graph, and the results above illustrate that we have some understanding of the distance 1 case. Our main question is: what happens in between? Question 1.8. What is the optimal size for forbidden induced or non-induced subgraphs, as a function of the verification radius and of the subgraph size?

It is very unclear what one should expect. Is it the case that, even with radius 2, the certificate size drops? Or on the contrary, one should see (almost) all the subgraphs in order to gain from a larger verification view? Note that increasing the verification radius beyond 1 means that the view of a vertex might contain a quadratic number of edges. This rules out the intuitive lower bound argument that the view at distance 1 of a node contains only at most 𝑛 edges and 𝑛 certificates, when 𝑛 2 bits of information is necessary. In this sense, the lower bounds are more difficult, and adding on top that we look for constructions that hold even for induced subgraphs, makes it especially challenging. Also, the increased radius allows for more fancy upper bound techniques, for example if some node would "naturally" receive a large certificate, we can cut it into pieces and distribute it to its neighbors to average the maximum certificate size.

Note that the idea of increasing the verification radius is not new: it has been introduced for constant radius (larger than 1) in [START_REF] Göös | Locally Checkable Proofs in Distributed Computing[END_REF], and non-constant radius in [START_REF] Feuilloley | Redundancy in distributed proofs[END_REF][START_REF] Ostrovsky | Space-Time Tradeoffs for Distributed Verification[END_REF], with recent new developments motivated by the so-called trade-off conjecture [START_REF] Bousquet | Local certification of local properties: tight bounds, trade-offs and new parameters[END_REF]. In this paper, the focus is slightly different, since the radius has to be compared to the subgraph size. In particular, questions like "can we go down to constant-size certificates if we look far enough?" are trivial to answer.

Additional discussion and motivation will be given in Section 1.4, after we describe our results.

Our results and techniques

The results of this paper are upper and lower bounds for certifying that a given subgraph does not appear in the network. The lower bound applies to any verification radius 𝑘, while the upper bounds apply for 𝑘 ⩾ 2.

Paths as benchmark. For concreteness, let us start with Table 1, that summarizes the different results we get for induced paths.

Forbidden induced subgraph Certificate size

Reference

𝑃 2𝑘 -1 0 Direct 𝑃 2𝑘+1 𝑂 (𝑛 log 𝑛) Discussion after Theorem 1.7 𝑃 3𝑘 -1 𝑂 (𝑛 log 3 𝑛) Theorem 1.12 𝑃 ⌈ 14 3 𝑘⌉ -1 𝑂 (𝑛 3/2 log 2 𝑛) Theorem 1.13 𝑃 4𝑘+3 Ω( 𝑛 𝑘 )
Theorem 1.9 We will see later in this section that several of our results hold for more general subgraphs (induced and non-necessarily induced), but paths are good as a benchmark, and all our techniques were first designed for paths and then generalized.

Let us make a few observations on this table before we review the theorems and techniques. A first observation is that all of these bounds are in the polynomial regime. Hence a general insight is that compact certifications do not exist for forbidden subgraphs, except for specific cases (e.g. 𝑃 4 -free graphs and non-necessarily induced trees) or for cases where we forbid several subgraphs (see the additional related work, Subsection 1.4). But, as argued earlier, there is an important difference between certifying with Θ(𝑛) bits and Θ(𝑛 2 ) bits, and in this regime, a lot can be done. A second observation is that our upper bounds are increasing faster when we increase the ratio between the path length and the radius, but without crashing into Θ(𝑛 2 ). This suggests that there might be a trade-off, although our lower bound does not allow such a parametrization. Finally, since our lower bound applies for paths of length at least 4𝑘 + 3, we do not rule out that below this length a very compact certification exist. We do not believe this to be true, and think that the right bound should be close to our upper bounds. Also note that we do have non-trivial polynomial upper and lower bounds for lengths between 4𝑘 + 3 and ⌈(14/3)𝑘⌉ -1.

Lower bounds. Our lower bound is the following. Theorem 1.9. When the vertices can see at distance 𝑘, at least Ω( 𝑛 𝑘 ) bits are needed to certify 𝑇 -free graphs, where 𝑇 is either 𝑃 4𝑘+3 or a tree of diameter at least 4𝑘 + 2 without degree 2 vertices.

While we designed our lower bound arguments to handle paths, we believe they can be extended to all trees of diameter at least 4𝑘 + 2, but the proof becomes more technical. To avoid too much technicalities, we rather extend it only to the trees without degree 2 vertices.

The general technique to establish this lower bound is inspired by the now classic reduction from non-deterministic communication complexity. There are actually several challenges to overcome for this to work with induced structures, but this discussion is deferred to Section 3.

Note that when restricting to radius 1, this theorem implies that 𝑃 7 -free graphs are hard to certify, while we already know that 𝑃 4 -free graphs are easy. We leave the remaining path lengths open.

Overview of our core upper bound technique. All our upper bounds use the same tool, that we call a layered map, which can be seen as a refinement of the so-called universal scheme (that we remind below). Just like the universal scheme, our layered maps are not specific to one type of task, and we believe they can be used in various contexts beyond subgraph finding. On the contrary, the tools we implement on top of these layered maps, are specific to subgraph detection.

Remember that in the universal scheme, the prover gives as certificate to every node the full map of the graph, and the vertices check that they have been given the same map as their neighbors, and that the map locally coincides with their neighborhoods. This takes 𝑂 (𝑛 log 𝑛 + min(𝑚 log 𝑛, 𝑛 2 )) bits (where 𝑚 is the number of edges), using adjacency matrix or adjacency lists. Now, to make use of the larger verification radius, we use an idea from [START_REF] Feuilloley | Redundancy in distributed proofs[END_REF], which is to spread the map. More precisely: on correct instances, the prover cuts the map into pieces and distribute it to the nodes of the graph in such a way all the vertices can see all the pieces in their neighborhood. Every vertex then simply reconstructs the map, and resumes the universal scheme.

This technique works well if the neighborhood at distance 𝑘 is large enough to drastically decrease the certificate size. This is the case for example when the minimum degree of the graph is polynomial, but in general this assumption is not met. Our layered map is a relaxed version of this spread universal scheme, where the nodes are given different certificates depending on their degree, and are able to check "partial maps" of the graph.

We describe the technique in the simpler setting with two groups of vertices, separating high and low degrees with a threshold of √ 𝑛, and we show how this can be used to prove the following theorem (which does not appear in Table 1 since it is superseded by better results). Theorem 1.10. We can certify 𝑃 4𝑘 -1 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 3/2 log 2 𝑛).

Intuitively, the high-degree vertices have enough neighbors to spread the whole map in their neighborhood, while the subgraph restricted to the low degree vertices is sparse enough to be given to all vertices (without spreading). The difficulty is that if the maps given to two high-degree vertices are not equal, and if these nodes are separated by enough low degree nodes, no node will be able to detect the inconsistency.

Actually, thanks to the radius 𝑘, if two high-degree vertices can be joined by hopping to highdegree vertices at distance at most 2𝑘, and the certification is accepted, then their maps must be identical. Therefore, we can define so-called extended connected components, or ECC for short, which partition the sets of high-degree vertices into groups that must have the same map. Our first technical work is to prove that we can certify exactly to all vertices the list of the ECCs, and how they partition the vertex set, with linear-size certificates.

We now sketch how to prove Theorem 1.10. Suppose that 𝐺 contains a path 𝑃 on 4𝑘 -1 vertices. Because different ECCs are at distance at least 2𝑘, such a path can touch zero, one or two ECCs. In the case of zero or one ECCs, the inconsistency issue raised earlier does not appear, and either the maps given are incorrect (and detected as incorrect), or they are correct and the vertices can see that they describe a graph with a long path. The case of two ECCs is more tricky. Essentially what we do is to give and certify for every node the length of the longest path starting from it and going towards the closest ECC. Along with other arguments, this ensures that at least one vertex will detect a long path touching two ECCs. (More details in Section 5.)

List of the forbidden subgraph upper bounds. It will be easier to sketch the proofs of our improved theorems once we will have formally described the layered maps, hence here we just list our results for reference, and refer to Section 5 for discussion of the proof techniques. Theorem 1.11. For every 𝑘 ⩾ 2, we can certify 𝐻 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 3/2 log 2 𝑛) for every 𝐻 of size at most 4𝑘 -1.

Actually, this theorem also holds for non-necessarily induced graphs. (The other theorems too, but it is not relevant since they are about paths, and we know Theorem 1.3). Theorem 1.12. For every 𝑘 ⩾ 2, we can certify 𝑃 3𝑘 -1 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 log 3 𝑛).

Theorem 1.13. For every 𝑘 ⩾ 2, we can certify 𝑃 ⌈ 14 3 𝑘⌉ -1 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 3/2 log 2 𝑛).

Additional related work and discussions

Certification size landscape. A fruitful line of work in the Local model consists in establishing the landscape of complexities for the classic family of problems called Locally checkable languages, LCLs for short; See e.g. [START_REF] Suomela | Landscape of Locality[END_REF]. In this perspective, one aims at characterizing the functions 𝑓 (𝑛) for which there exists a problem whose optimal complexity is 𝑓 (𝑛). Developing the same kind of theory for local certification size is an exciting research direction. So far, the only sizes for which we have natural problems with tight bounds are: 𝑂 (1), Θ(log 𝑛), Θ(𝑛) and Θ(𝑚), where Θ means up to subpolynomial factors. (One can actually build a problem for any size 𝑓 (𝑛, 𝑚) above log 𝑛, but it is artificial in the sense that the definition of the problem refers to the function 𝑓 .)

The constant certification size regime contains local properties such as coloring (intuitively the LCLs), and the dependency in other parameters such as the maximum degree has been explored very recently [START_REF] Bousquet | Local certification of local properties: tight bounds, trade-offs and new parameters[END_REF]. The size Θ(log 𝑛) is very common, with the archetypal problem being acylicity. See for example the list of problems in [START_REF] Göös | Locally Checkable Proofs in Distributed Computing[END_REF], and the recent series of papers establishing meta-theorems for this regime [START_REF] Feuilloley | What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs[END_REF][START_REF] Fraigniaud | Distributed Certification for Classes of Dense Graphs[END_REF][START_REF] Fraigniaud | A Meta-Theorem for Distributed Certification[END_REF]. Actually, in some of these papers, the upper bounds are polylogs and not logs, and they are not matching the lower bounds, leaving open whether some of these properties have optimal certificate size Θ(log 𝑐 𝑛), with 𝑐 > 1, or not. 7 Finally, in the polynomial regime, we know problems with complexity Θ(𝑛) (e.g. diameter ⩽ 3 [START_REF] Censor-Hillel | Approximate proof-labeling schemes[END_REF]) and problems with complexity Θ(𝑚) (e.g. symmetric graphs [START_REF] Göös | Locally Checkable Proofs in Distributed Computing[END_REF] and non-3-colorable graphs [START_REF] Göös | Locally Checkable Proofs in Distributed Computing[END_REF]). Our paper explores the polynomial regime, but unfortunately since the bounds do not match we cannot conclude for sizes between 𝑛 and 𝑚. Nevertheless, we believe that the case of induced paths of various sizes is a promising direction in this landscape perspective.

Certification of graph classes and forbidden subgraphs.

A recent trend in local certification has been to focus on certifying graph property (e.g. planarity) instead of certifying the output of an algorithm (e.g. that a set of pointers distributed on the nodes collectively form a spanning tree). Two motivations behind this focus are that the optimal certification size can be seen as a measure the locality of a graph property (raising interest from the graph theory community) and that algorithms tailored to work on specific graph classes make more sense if one can ensure that the graph indeed belongs to the class.

Among the classes studied, many are defined by forbidden minors, as discussed after Conjecture 1.1. But some of these classes are not closed under minors, and are better described by families of forbidden induced subgraphs. For example, the authors of [START_REF] Jauregui | Local Certification of Some Geometric Intersection Graph Classes[END_REF] tackle the case of chordal graphs (that are characterized by forbidding all induced cycles of length at least 4) and several other classes whose subgraph characterizations are more cumbersome: interval graphs, circular arc graphs, trapezoid graphs and permutation graphs. For all these classes, [START_REF] Jauregui | Local Certification of Some Geometric Intersection Graph Classes[END_REF] establishes a 𝑂 (log 𝑛)-bit certification. This might come as a surprise, since in this paper all the certifications are in the polynomial regime. The reason for this contrast is that all the classes we have just mentioned are very structured, and in particular have geometric representations, which can be used for certification. Very recently, it was proved that some classes are hard to certify even though they do have geometric representation: 1-planar graphs, unit disk graphs and other related classes require (quasi)-linear-in-𝑛 certificates [START_REF] Defrain | Local certification of geometric graph classes[END_REF].

Techniques based on bucketing by degree. As said earlier, our layered maps are based on bucketing the vertices by degree. This is a classic step in distributed subgraph detection. A classic canvas for detection algorithm is to first process the high-degree nodes, either arguing that there are few of them (see e.g. [START_REF] Fischer | Possibilities and Impossibilities for Distributed Subgraph Detection[END_REF]) or that many nodes are close to high degree nodes (see e.g. [START_REF] Censor-Hillel | Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs[END_REF]), and then to process low-degree nodes, often using color coding (a large part of these algorithms is randomized). Another technique consists in computing an expander (or conductance) decomposition, to separate the graph into parts that are well-connected (where one can basically compute as if the cluster would be a clique) and parts of low degree (see e.g. [START_REF] Chang | Distributed Triangle Detection via Expander Decomposition[END_REF][START_REF] Eden | Sublinear-time distributed algorithms for detecting small cliques and even cycles[END_REF]).

Our understanding is that only general intuitions can be transfered from these algorithms to our setting, namely: inside a cluster one should use the fact that it is easy to move/distribute information, whereas in low-degree parts one should enjoy the fact that there are fewer edges, hence fewer information to spread.

MODEL AND DEFINITIONS

Graph theory notions

In this paper, the network is modeled by an undirected graph without loops or parallel edges. The number of nodes is denoted by 𝑛 and the number of edges is denoted by 𝑚. A graph is 𝑑-regular if all its vertices have degree 𝑑. A graph is regular if it is 𝑑-regular for some 𝑑.

We call 𝐻 an induced subgraph of 𝐺 if 𝐻 is obtained from 𝐺 by deleting a subset of the vertices of 𝐺 and the edges incident to them. We call a graph 𝐻 -free if it does not contain 𝐻 as an induced subgraph. We call 𝐻 a subgraph (sometimes specified as non-necessarily induced) of 𝐺 if 𝐻 is obtained from 𝐺 by deleting a subset of the vertices of 𝐺, the edges incident to them, and an arbitrary subset of edges of 𝐺. We let 𝑃 𝑘 , 𝐶 𝑘 denote the path and cycle on 𝑘 vertices respectively. The length of a path or cycle is the number of its edges.

We say two disjoint sets of vertices 𝑋, 𝑌 are complete to each other if all possible edges between 𝑋 and 𝑌 are present. If there are no edges between 𝑋 and 𝑌 we say they are anticomplete. A set of edges 𝑀 of a bipartite graph 𝐺 is a perfect matching if all the vertices of the graph are adjacent to exactly one edge of 𝑀. A set of edges in a bipartite graph is an antimatching, if they form a complete bipartite graph without a perfect matching.

Local certification

In the networks we consider, the vertices are equipped with unique identifiers on 𝑂 (log 𝑛) bits. Certificates are labels attached to the vertices. The view at distance 𝑑 of a vertex 𝑣 consists of: (1) the vertices at distance at most 𝑑 from 𝑣, (2) the identifiers and certificates of these vertices, and (3) the edges between these vertices, except the ones between two vertices at distance exactly 𝑑. Definition 2.1. We say that there exists a local certification at distance 𝑑 of size 𝑠 for a property 𝑃 if there exists a local algorithm (called the verification algorithm) taking as input on every node 𝑣 the view at distance 𝑑, and outputting accept/reject such that:

• For every graph that satisfies the property 𝑃, there exists a certificate assignment, with certificates of size at most 𝑠 (𝑛), such that the verification algorithm accepts at every node. • For every graph that does not satisfy the property 𝑃, for all certificate assignments, there exists at least one node where the verification algorithm rejects.

In order to facilitate the writing, we say that the certificates are given by a prover. We can specify how the certificates are assigned by the prover on correct instances (i.e. graphs satisfying the property 𝑃), but we cannot control what happens on incorrect instances.

As an example, let us describe a local certification at distance 1, with certificate size 𝑂 (log 𝑛), for checking that the graph is acyclic. On a correct instance, the prover chooses a node to be the root, and gives as a certificate to every node its distance to the root. The verification algorithm checks that the distances are consistent (typically that one neighbor has been assigned a strictly smaller distance, and the others a strictly larger distance). Now if the graph has a cycle, for any certificate assignment, the vertex with the largest assigned distance in the cycle has at least two vertices with distance smaller than or equal to its distance, hence it rejects.

LOWER BOUND FOR PATHS

In this section, we prove the following theorem. Theorem 1.9. When the vertices can see at distance 𝑘, at least Ω( 𝑛 𝑘 ) bits are needed to certify 𝑇 -free graphs, where 𝑇 is either 𝑃 4𝑘+3 or a tree of diameter at least 4𝑘 + 2 without degree 2 vertices. Discussion of the challenges and features of the proof. At first sight, the proof of this theorem is a reduction from the problem of non-disjointness in non-deterministic communication complexity, which is now a classic tool in the area. We would like to highlight several challenges and new features. First, we actually do not use communication complexity: we use a simple counting argument, avoiding defining all the non-deterministic Alice-Bob set-up, and demystifying the core of the argument. Second, the construction itself is very delicate. In classic proofs of the same flavor (e.g. [START_REF] Censor-Hillel | Approximate proof-labeling schemes[END_REF][START_REF] Feuilloley | Redundancy in distributed proofs[END_REF]), one usually deals with a radius 𝑘 view in a very simple way: just replacing every edge with a path of length 𝑘. This is no good for us since we want to control very precisely the path structure of the graph. Also, we need to care about non-edges everywhere in the construction and not only in the part "encoding the disjointness". Indeed, non-edges are crucial, since we know from Theorem 1.3 that for non-necessarily induced paths, such a lower bound cannot hold. These difficulties translate into a construction that blends cliques, matchings and antimatchings, and a proof that requires a careful case analysis to rule out unexpected paths.

Proof. Let 𝑘, 𝑛 ∈ N, and 𝑇 be either 𝑃 4𝑘+3 or a tree of diameter at least 4𝑘 + 2 without degree 2 vertices. Let 𝐻, 𝐻 ′ be two bipartite graphs on the same vertex set {0, 1} × {1, . . . , 𝑛}. To have lighter notations, we denote an edge by (𝑖, 𝑗) instead of ((0, 𝑖), (1, 𝑗)). Assume moreover that 𝐻 satisfies the two following properties:

(i) For all (𝑖, 𝑗) ∈ {1, . . . , 𝑛} 2 , (𝑖, 𝑗) ∈ 𝐻 if and only if ( 𝑗, 𝑖) ∈ 𝐻 (𝐻 is symmetric) (ii) For all 𝑖 ∈ {1, . . . , 𝑛}, (𝑖, 𝑖) ∈ 𝐻 (𝐻 is reflexive) and the same holds for 𝐻 ′ . We will construct a graph 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ) on 4𝑘 (𝑛 -1) + |𝑇 | vertices, which is 𝑇 -free if and only if 𝐻 and 𝐻 ′ do not have a common non-edge. The construction is illustrated on Figure 1.

Let us construct the graph 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ) in the following way. We construct 4𝑘 cliques of size 𝑛, denoted by 𝐾 0 1 , . . . 𝐾 0 2𝑘 , 𝐾 1 1 , . . . 𝐾 1 2𝑘 . In each clique, we number the vertices from 1 to 𝑛. 8 For every clique 𝐾 and 𝑖 ∈ {1, . . . , 𝑛}, we denote by 𝐾 [𝑖] the vertex numbered by 𝑖 in 𝐾. We add the following edges in 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ):

• We put the bipartite graph 𝐻 between 𝐾 0 1 and 𝐾 1 1 , and 𝐻 ′ between 𝐾 0 2𝑘 and 𝐾 1 2𝑘 .9 • For every 𝑗 ∈ {2, . . . , 2𝑘 -1}, we put the perfect matching {(𝐾 0 𝑗 [𝑖], 𝐾 We state the main property satisfied by this construction in Proposition 3.1 below. We prove Proposition 3.1 by looking carefully at the structure of 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ) at the end of this section.

Loosely speaking, the reason we require 𝐻 and 𝐻 ′ to be symmetric is because we want the cliques 𝐾 0 ℓ and 𝐾 1 ℓ to play the same "roles" in the graph for each ℓ ∈ {1, 2, . . . , 2𝑘 }. Proposition 3.1. The graph 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ) is 𝑇 -free if and only if 𝐻 and 𝐻 ′ do not have a common non-edge (𝑖, 𝑗) with 𝑖, 𝑗 ∈ {1, 2, . . . , 𝑛} 2 .

Let us prove Theorem 1.9 using Proposition 3.1. Assume that 𝑚 bits are sufficient to certify 𝑇 -free graphs when vertices can see at distance 𝑘. For any 𝐻, 𝐻 ′ , let 𝑉 denote the vertex set of 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ).

We first define a family of positive instances. Let 𝐻 denote the bipartite graph obtained from 𝐻 by replacing all edges (𝑖, 𝑗) of 𝐻 with non-edges and vice versa for any two distinct 𝑖, 𝑗 ∈ {1, 2, . . . , 𝑛}. That is 𝐸 (𝐻 ) = ({1, 2, . . . , 𝑛} 2 \ 𝐸 (𝐻 )) ∪ {(𝑖, 𝑖)} 1⩽𝑖 ⩽𝑛 . Note that 𝐻 is symmetric and reflexive, and that 𝐻 and 𝐻 have no common non-edge, by construction. Then, by Proposition 3.1, for every bipartite graph 𝐻 which is symmetric and reflexive, the graph 𝐺 𝑘,𝑛 (𝐻, 𝐻 ) is 𝑇 -free. Therefore, by hypothesis, there exists a certificate function 𝑐 𝐻 : 𝑉 → {0, . . . , 2 𝑚 -1} such that all the vertices in 𝐺 𝑘,𝑛 (𝐻, 𝐻 ) accept. Claim 3.2. For any two distinct symmetric and reflexive graphs 𝐻, 𝐻 ′ on 𝑉 , 𝑐 𝐻 ≠ 𝑐 𝐻 ′ Proof. Suppose that there are two different bipartite graphs 𝐻 and 𝐻 ′ satisfying the conditions above, such that 𝑐 𝐻 = 𝑐 𝐻 ′ . Since 𝐻 ≠ 𝐻 ′ , we have either 𝐸 (𝐻 ) ⊈ 𝐸 (𝐻 ′ ) or 𝐸 (𝐻 ) ⊈ 𝐸 (𝐻 ′ ) or both. By symmetry, assume that 𝐸 (𝐻 ) ⊈ 𝐸 (𝐻 ′ ). Then, the graph 𝐺 𝑘,𝑛 (𝐻 ′ , 𝐻 ) is accepted with 𝑐 𝐻 . Indeed, the vertices in the cliques 𝐾 𝑖 𝑗 for 𝑖 ∈ {0, 1} and 𝑗 ∈ {1, . . . , 𝑘 }, or pending from these cliques have the same view as their view in 𝐺 𝑘,𝑛 (𝐻 ′ , 𝐻 ′ ) since the only part of the graph which has changed between 𝐺 𝑘,𝑛 (𝐻 ′ , 𝐻 ′ ) and 𝐺 𝑘,𝑛 (𝐻 ′ , 𝐻 ′ ) is the bipartite graph between 𝐾 0 2𝑘 and 𝐾 1 2𝑘 , which is at distance at least 𝑘 from them. Thus, these vertices accept in 𝐺 𝑘,𝑛 (𝐻 ′ , 𝐻 ′ ). Similarly, 𝑤 and the vertices in the cliques 𝐾 𝑖 𝑗 for 𝑖 ∈ {0, 1} and 𝑗 ∈ {𝑘 + 1, . . . , 2𝑘 } or pending from them have the same view in 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ) and 𝐺 𝑘,𝑛 (𝐻 ′ , 𝐻 ′ ), so they accept in the graph 𝐺 𝑘,𝑛 (𝐻 ′ , 𝐻 ′ ) as well. However, since 𝐻 ⊈ 𝐻 ′ , the graphs 𝐻 ′ and 𝐻 ′ have a common non-edge, hence 𝐺 𝑘,𝑛 (𝐻 ′ , 𝐻 ′ ) is not 𝑇 -free (by Proposition 3.1), which is a contradiction. ■

There are 2

𝑛 (𝑛-1) 2
such symmetric and reflexive bipartite graphs 𝐻 on 𝑉 , and there are at most 2 𝑚 (4𝑘𝑛+|𝑇 | ) functions 𝑉 → {0, . . . , 2 𝑚 -1}. Thus, by Claim 3.2, we get 2

𝑛 (𝑛-1) 2 ⩽ 2 𝑚 (4𝑘𝑛+|𝑇 | )
, which finally gives us 𝑚 = Ω( 𝑛 𝑘 ). □

Let us now turn to the proof of Proposition 3.1. We will need the following result about the shape of long paths in 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ). For succinctness, we will call 𝐾 0 1 , . . . 𝐾 0 2𝑘 , 𝐾 1 1 , . . . 𝐾 1 2𝑘 the cliques (of 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ )) throughout this section. Lemma 3.3. Let 𝑇 be an induced tree in 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ). Then, 𝑇 has at most 4𝑘 vertices in the cliques.

Proof of Lemma 3.3. The main ingredient of the proof of Lemma 3.3 is the following Claim 3.4. In the following, two cliques are said to be antimatched if there is an antimatching between them (that is, between the first and the second clique, there is a complete bipartite graph except for 𝑛 independent non-edges). • We now prove property (ii). Let 𝐾 = 𝐾 𝑖 𝑗 and 𝐾 ′ = 𝐾 1-𝑖 𝑗 . Assume for a contradiction that there exist two distinct 𝑠, 𝑡 ∈ {1, 2, . . . , 𝑛} such that 𝐾 ′ [𝑠] and 𝐾 ′ [𝑡] are both in 𝑇 . Note that since 𝑇 is triangle-free, if 𝑗 = 1 then 𝑇 cannot contain 𝑣 0 nor 𝑣 1 , and if 𝑗 = 2𝑘, then 𝑇 cannot contain 𝑤. Therefore, since 𝑇 has at least 5 vertices, it follows that there is some We are now ready to conclude the proof of Lemma 3.3. Assume by contradiction that 𝑇 has at least 4𝑘 + 1 vertices in the cliques. By the pigeonhole principle, there exists 𝑗 ∈ {1, . . . , 𝑘 } such that 𝑇 has at least 5 vertices in the cliques 𝐾 := 𝐾 0 2𝑗 -1 , 𝐾 ′ := 𝐾 1 2𝑗 -1 , 𝐾 ′′ := 𝐾 0 2𝑗 , 𝐾 ′′′ := 𝐾 1 2𝑗 . Again by the pigeonhole principle, 𝑇 has at least 2 vertices in one of these four cliques, and by Claim 3.4, exactly 2. By symmetry, assume that 𝑇 has two vertices in 𝐾 (see Figure 3 for an illustration). Then, by (i) and (ii) of Claim 3.4, 𝑇 has at most one vertex in each of the cliques 𝐾 ′ , 𝐾 ′′ , 𝐾 ′′′ , so exactly one in each (because 𝑇 contains five vertices in the union of these four cliques). Let us denote by 𝐾 [𝑥], 𝐾 [𝑦] these two vertices in 𝐾 ∩ 𝑇 , and by 𝐾 ′ [𝑥 ′ ], 𝐾 ′′ [𝑥 ′′ ], 𝐾 ′′′ [𝑥 ′′′ ] the vertices of 𝑇 in 𝐾 ′ , 𝐾 ′′ , 𝐾 ′′′ respectively. Since 𝑇 is an induced tree, we have 𝑥 ′′ = 𝑥 or 𝑥 ′′ = 𝑦 (else, {𝑥, 𝑦, 𝑥 ′′ } would be a triangle, since 𝐾 ′′ is antimatched with 𝐾). By symmetry, we can assume that 𝑥 ′′ = 𝑥. Similarly, we have 𝑥 ′′′ = 𝑥 or 𝑥 ′′′ = 𝑦. In the former case,

𝐾 ′′ ∈ {𝐾 0 𝑗 -1 , 𝐾 1 𝑗 -1 , 𝐾 0 𝑗+1 , 𝐾 1 𝑗+1 } such that 𝑇 contains 𝐾 ′′ [𝑧] for some 𝑧 ∈ {1, 2
𝐾 [𝑦]-𝐾 ′′ [𝑥]-𝐾 ′′′ [𝑥]-𝐾 [𝑦] is a triangle in 𝑇 . Hence, we have 𝑥 ′′′ = 𝑦.
Finally, there are two cases, depicted in Figure 3, which are the following:

• If 𝑥 ′ ∈ {𝑥, 𝑦}, assume by symmetry that 𝑥 ′ = 𝑥. Then, 𝐾 [𝑥]-𝐾 ′ [𝑥]-𝐾 ′′′ [𝑦]-𝐾 [𝑥] is a triangle in 𝑇 , a contradiction. • If 𝑥 ′ ∉ {𝑥, 𝑦},
then 𝑇 has a 𝐶 5 as a subgraph. This is a contradiction. □

We are finally able to prove Proposition 3.1. We start by the case of paths, and then extend the proof to handle the other case.

Proof of Proposition 3.1 for 𝑃 4𝑘+3 . Assume first that 𝐻 and 𝐻 ′ have a common non-edge. Let (𝑖, 𝑗) be this common non-edge. By reflexivity of 𝐻 and 𝐻 ′ , we have 𝑖 ≠ 𝑗. Then, we can construct an induced path of length 4𝑘 + 3 as follows:

𝑣 0 , 𝐾 0 1 [𝑖], 𝐾 0 2 [ 𝑗], 𝐾 0 3 [𝑖], . . . , 𝐾 0 2𝑘 [ 𝑗] (alternating between 𝑖 and 𝑗), 𝑤, 𝐾 1 2𝑘 [𝑖], 𝐾 1 2𝑘 -1 [ 𝑗], 𝐾 1 2𝑘 -2 [𝑖], . . . , 𝐾 1 1 [ 𝑗], 𝑣 1 .
This path is depicted on Figure 4. Note that since (𝑖, 𝑗) is a non-edge in 𝐻 ′ which is symmetric, then ( 𝑗, 𝑖) is also a non-edge in 𝐻 ′ . Thus, it is indeed an induced path.

Conversely, assume that there is an induced path 𝑃 on 4𝑘 + 3 vertices in 𝐺 𝑛,𝑘 (𝐻, 𝐻 ′ ), and let us show that 𝐻, 𝐻 ′ have a common non-edge. By Lemma 3.3, 𝑃 has at most 4𝑘 vertices in the cliques, and since there are exactly 3 vertices outside the cliques, 𝑃 has exactly 4𝑘 vertices in the cliques, and it uses all the vertices outside of the cliques, namely 𝑣 0 , 𝑣 1 , 𝑤. Note that the neighborhoods of 𝑣 0 and 𝑣 1 in 𝐺 𝑛,𝑘 (𝐻, 𝐻 ′ ) are cliques, hence they must have degree 1 in 𝑃 so they are the two endpoints of 𝑃. So 𝑃 starts with 𝑣 0 , 𝑥 1 ∈ 𝐾 0 1 , and ends with 𝑣 1 , 𝑦 1 ∈ 𝐾 1 1 . Since 𝑤 ∈ 𝑉 (𝑃) is not an end of 𝑃 it must have degree two in 𝑃. Hence, for some 𝑖, 𝑗 ∈ {1, 2, . . . , 𝑛}, 𝐾

0 2𝑘 [ 𝑗], 𝐾 1 2𝑘 [𝑖] are the neighbors of 𝑤 in 𝑉 (𝑃). 𝐾 0 2𝑘 [𝑖], 𝐾 1 2𝑘
[ 𝑗] must be non-adjacent, so ( 𝑗, 𝑖) is not an edge of 𝐻 ′ . Since 𝐻 is reflexive it follows that 𝑖 ≠ 𝑗 and since it is symmetric (𝑖, 𝑗) is not an edge of 𝐻 ′ . Proof. Let ℓ ∈ {1, 2, . . . , 2𝑘 -1} be maximum such that the claim does not hold for ℓ. By symmetry, we may assume that both 𝑥 := 𝐾 0 ℓ+1 [ 𝑗], 𝑦 := 𝐾 1 ℓ+1 [𝑖] are elements of 𝑉 (𝑃). Since 𝑣 0 , 𝑣 1 are the ends of 𝑃, both 𝑥, 𝑦 must have a neighbor in 𝐾 0 ℓ ∪ 𝐾 1 ℓ . In particular, there must be vertices 𝑥 ′ , 𝑦 ′ ∈ 𝐾 0 ℓ ∪ 𝐾 1 ℓ so that (𝑥, 𝑥 ′ ), (𝑦, 𝑦 ′ ) and there are no further edges between vertices in {𝑥, 𝑥 ′ , 𝑦, 𝑦 ′ }. By construction for each 𝐾 ∈ {𝐾 0 ℓ , 𝐾 1 ℓ } and 𝐾 ′ ∈ {𝐾 0 ℓ+1 , 𝐾 1 ℓ+1 }, there is an antimatching between 𝐾 and 𝐾 ′ . So in particular, either

𝑥 ′ = 𝐾 0 ℓ [𝑖] and 𝑦 ′ = 𝐾 1 ℓ [ 𝑗] or 𝑥 ′ = 𝐾 1 ℓ [𝑖] and 𝑦 ′ = 𝐾 0 ℓ [ 𝑗]. ■
Thus by Claim 3.5 and since 𝐻 is symmetric, (𝑖, 𝑗) is a non-edge of 𝐻 . So 𝐻 and 𝐻 ′ have a common non-edge as desired.

□

We may now adapt this proof to handle the case of trees without vertices of degree 2.

Proof of the remaining case of Proposition 3.1. If 𝐻 and 𝐻 ′ share a common non-edge, then by the previous proof, there is an induced path on 4𝑘 + 3 vertices in 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ) as depicted on Figure 4. Adding all the vertices outside of the cliques to this path yields a copy of 𝑇 .

Conversely, assume that there is an induced copy of 𝑇 in 𝐺 𝑛,𝑘 (𝐻, 𝐻 ′ ), and let us show that 𝐻, 𝐻 ′ have a common non-edge. By Lemma 3.3, 𝑇 has at most 4𝑘 vertices in the cliques, and since there are exactly |𝑉 (𝑇 )| -4𝑘 vertices outside the cliques, 𝑇 has exactly 4𝑘 vertices in the cliques, and it uses all the vertices outside of the cliques. In particular, by connectivity, 𝑇 must contain at least a vertex in each clique (hence exactly once). Using this, we can show that Claim 3.5 still holds in this case, which concludes. □

UPPER BOUND CORE TECHNIQUE: LAYERED MAPS

Spread universal certification and graphs of large minimum degree

We have described in Subsection 1.3 the general idea of layered maps, which are a refinement of the technique of spreading the certificate of the universal scheme. We formalize the spread universal scheme (introduced in [START_REF] Feuilloley | Redundancy in distributed proofs[END_REF]) in the following theorem.

Theorem 4.1.

(i) Let 𝛿 < 1. Any property can be certified with certificates of size 𝑂 (𝑛 2-𝛿 log 𝑛) on graphs of minimum degree 𝑛 𝛿 if vertices can see at distance 2.

(ii) Any property can be certified with certificates of size 𝑂 (𝑛 log 2 𝑛) on regular graphs if vertices can see at distance 2.

Before giving the proof, we give a short sketch for the case of the first item. On correct instances, the prover computes the certificate of the universal scheme in the form of an adjacency matrix, cuts it into 𝑛 𝛿 pieces of size 𝑛 2-𝛿 , and gives 𝑂 (log 𝑛) pieces to every node, in such a way that each vertex can see all the pieces in its neighborhood. Such an assignment of pieces is proved to exist via probabilistic method and coupon collector. Note that we need the distance to be at least two, only to ensure that every node can check that the graph it reconstructs is the same as its neighbors.

Before proving Theorem 4.1, we show the following Lemma 4.2 (inspired from the coupon collector theorem), that we will use several times. Lemma 4.2. Let 𝐺 be a 𝑛-vertex graph and 0 < 𝑑 < 𝑛. Let P be a set of size 𝑑, called the set of pieces. Then, there exists a way to assign 3 log 𝑛 pieces to every vertex of 𝐺 such that, for every vertex 𝑢 of degree at least 𝑑, each piece of P has been given to 𝑢 or one of its neighbors.

Proof. Let us consider a random assignation of the pieces to the vertices of 𝐺, where each vertex gets assigned a subset of P of size 3 log 𝑛 pieces (uniformly at random, independently of all the other vertices). Let us fix some piece 𝑝 ∈ P and some vertex 𝑢 of degree at least 𝑑. Observe that the probability that 𝑝 has not been given to 𝑢 not to its neighbors is at most:

1 - 3 log 𝑛 𝑑 𝑑 ⩽ 𝑒 -3 log 𝑛 ⩽ 1 𝑛 3
. By union bound, the probability that such an event occurs for some vertex 𝑢 of degree at least 𝑑 and some piece 𝑝 ∈ P is at most 1 𝑛 . This is strictly smaller than 1 for all 𝑛 ⩾ 2. Thus, there exists some correct assignment of the pieces. □

We may now proceed with the proof of Theorem 4.1.

Proof of Theorem 4.1.

(i) Let us describe a certification scheme of size 𝑂 (𝑛 2-𝛿 log 𝑛) for any property, in graphs of minimum degree 𝑛 𝛿 , if vertices can see at distance 2. Let 𝐺 = (𝑉 , 𝐸) be a graph with |𝑉 | = 𝑛, and minimum degree 𝑛 𝛿 .

Certification. The prover assigns to each vertex 𝑢 a certificate divided in two fields: one common to every node (denoted by SpanningTree), and another specific to 𝑢 (denoted by Pieces(𝑢)).

• In SpanningTree, the prover writes a spanning tree T of 𝐺, that is: the identifiers of the vertices and of their parent in T . This uses 𝑂 (𝑛 log 𝑛) bits. • For Pieces, the prover cuts the adjacency matrix of 𝐺 in 𝑛 𝛿 parts, each of size 𝑛 2-𝛿 , and number these parts from 1 to 𝑛 𝛿 . Then, using Lemma 4.2, since all the vertices have degree at least 𝑛 𝛿 , it may write 3 log 𝑛 numbered pieces in each Pieces(𝑢) such that every vertex sees each piece at least once in its closed neighborhood. This certificate has size 𝑂 (𝑛 2-𝛿 log 𝑛).

Verification. The verification algorithm of each vertex 𝑢 is done in two steps.

• The first step is to check the correctness of SpanningTree. To do so, 𝑢 checks if SpanningTree is the same in its certificate and the certificate of all its neighbors. Then, it checks if it is indeed a tree, and if each of its neighbors in SpanningTree is also a neighbor in 𝐺. If it is not the case, 𝑢 rejects. If no vertex rejects at this point, SpanningTree is a correct spanning tree known by all the vertices. In particular, every vertex 𝑢 knows 𝑛, the number of vertices in 𝐺. • The second and main step of the verification is the following. Since 𝑢 knows 𝑛, 𝑢 knows the number pieces (which is 𝑛 𝛿 ). The vertex 𝑢 checks if it sees each numbered piece appears in Pieces(𝑣) for some vertex 𝑣 in its closed neighborhood, and rejects if it is not the case. If 𝑢 did not reject, it may thus reconstruct the whole graph 𝐺, and can also recover the graph reconstructed by every of its neighbors since it sees at distance at least 2. If some of these reconstructed graphs are different, 𝑢 rejects. Then, 𝑢 checks if its neighborhood is correctly written in its reconstructed graph. Finally, if 𝑢 did not reject before, it accepts if and only if its reconstructed graph satisfies the property.

Correctness. If no vertex rejects in the verification procedure, all the vertices reconstructed the same graph. Moreover, this reconstructed graph is equal to 𝐺, because every vertex checked that its neighborhood is correct in it. Since every vertex accepts if and only if this graph satisfies the property, the scheme is correct. (ii) Let us now describe a certification scheme of size 𝑂 (𝑛 log 2 𝑛) for any property in regular graphs, if vertices can see at distance 2. Let 𝐺 be an 𝑛-vertex 𝑑-regular graph.

Certification. The certification is similar to the proof of (i), except that since 𝐺 is a 𝑑-regular graph, it can be represented with 𝑂 (𝑑𝑛 log 𝑛) bits using adjacency lists (instead of the adjacency matrix). The prover cuts it in 𝑑 pieces, each of size 𝑂 (𝑛 log 𝑛), numbers them from 1 to 𝑑, and applies Lemma 4.2 to assign 3 log 𝑛 pieces in the certificate of every vertex. This yields certificates of size 𝑂 (𝑛 log 2 𝑛).

Verification. The verification algorithm is the following one. Every vertex 𝑢 knows its own degree, which is equal to the number of pieces. So 𝑢 can check if it sees all the pieces in its closed neighborhood. Then, as for (i), 𝑢 reconstructs the whole graph 𝐺 and checks if all its neighbors reconstructed the same graph. Finally, 𝑢 checks if its own neighborhood is correctly written, and if the property is satisfied.

Correctness.

As for (i), if no vertex rejects in the verification procedure, all the vertices computed the same graph, which is equal to 𝐺 and satisfies the property. □

Definitions: extended connected components, ECC table, and more

We now introduce formally the layered map, that we have informally described in the introduction, along with other related notions.

Definitions.

Extended connected components. Let 𝜀 > 0 and 𝑁 = ⌈ 1 𝜀 ⌉. We consider the following partition of the vertices depending on their degrees: for every 𝑖 ∈ {1, . . . , 𝑁 }, let 𝑉 𝑖 := {𝑢 ∈ 𝑉 | 𝑛 (𝑖 -1)𝜀 ⩽ 𝑑𝑒𝑔(𝑢) < 𝑛 𝑖𝜀 } (where 𝑑𝑒𝑔(𝑢) is the degree of the vertex 𝑢). Note that the sets 𝑉 1 , . . . , 𝑉 𝑁 form a partition of 𝑉 . Let 𝐿 𝑖 := 𝑗 ⩽𝑖 𝑉 𝑖 , that is, 𝐿 𝑖 is the set of vertices having degree less than than 𝑛 𝑖𝜀 . And let 𝐻 𝑖 := 𝑗 ⩾𝑖 𝑉 𝑖 , that is, 𝐻 𝑖 is the set of vertices having degree at least 𝑛 (𝑖 -1)𝜀 (it is also 𝑉 \𝐿 𝑖 -1 ). Note that 𝐻 1 = 𝐿 𝑁 = 𝑉 .

Let 𝑘 ⩾ 2, the distance up to which the vertices can see in the certification scheme. For each 𝑖 ∈ {1, . . . , 𝑁 }, we partition 𝐻 𝑖 in subsets called extended connected components of 𝐻 𝑖 (abbreviated by ECC 𝑖 ). For 𝑢, 𝑣 ∈ 𝐻 𝑖 we say 𝑢, 𝑣 are 𝑖-linked if there is a 𝑢, 𝑣 path in 𝐺 which does not have 2𝑘 -2 consecutive vertices in 𝐿 𝑖 -1 (in other words, such a path should regularly contain vertices in 𝐻 𝑖 ). An ECC 𝑖 is a maximal subset of vertices of 𝐻 𝑖 which are pairwise 𝑖-linked. Note that being 𝑖-linked is an equivalence relation. By definition, two vertices in two different ECC 𝑖 's are at distance at least 2𝑘 -1 from each other in 𝐺.

Let us denote by E 𝑖 the set of all ECC 𝑖 's (which is a partition of 𝐻 𝑖 ). For each 𝐶 ∈ E 𝑖 , we define the identifier of C, denoted by 𝑖𝑑 (𝐶), as the smallest identifier of a vertex in 𝐶. Finally, we denote by 𝐶 (𝑑) the set of vertices at distance exactly 𝑑 from 𝐶 (by convention, we set 𝐶 (0) := 𝐶). Note that 𝐶 (0) ⊆ 𝐻 𝑖 , and for all 𝑑 ⩾ 1, we have 𝐶 (𝑑) ⊆ 𝐿 𝑖 -1 = 𝑉 (𝐺) \ 𝐻 𝑖 .

Note that for every 𝑢 ∉ 𝐻 𝑖 there is at most one 𝐸𝐶𝐶 𝑖 𝐶 ∈ E 𝑖 such that 𝑢 is at distance at most 𝑘 -1 from 𝐶. In other words, for each 𝑖 ∈ {1, . . . , 𝑁 }, the partition of 𝐻 𝑖 in ECC 𝑖 's is written in the table 𝑇 𝐺 , and for every vertex 𝑢 ∈ 𝐿 𝑖 -1 "close" to some 𝐶 𝑢 ∈ E 𝑖 , the distance from 𝑢 to 𝐶 𝑢 is also stored in 𝑇 𝐺 .

ECC-

Witnessed graph. We define a relation ≼ on 𝑉 in the following way. Let 𝑢, 𝑣 ∈ 𝑉 . We say that 𝑣 ≼ 𝑢 if there exists 𝑖 ∈ {1, . . . , 𝑁 } such that 𝑣 ∈ 𝑉 𝑖 , 𝑢 ∈ 𝐻 𝑖 , and 𝑢, 𝑣 are in the same ECC 𝑖 . Note that, by definition, ≼ is transitive. For every 𝑢 ∈ 𝑉 , let 𝑉 ≼𝑢 be the set {𝑣 ∈ 𝑉 | 𝑣 ≼ 𝑢}, called the set of vertices witnessed by 𝑢. Let 𝐺 ≼𝑢 be the subgraph of 𝐺 obtained by keeping only edges having at least one endpoint in 𝑉 ≼𝑢 , which is called the graph witnessed by 𝑢. Intuitively, if 𝑣 ∈ 𝑉 ≼𝑢 , then 𝑢 can check all the adjacencies of 𝑣 thanks to the certificates (see Theorem 4.5).

Local computation scheme. Now, let us introduce the notion of local computation scheme. Informally, it is a tool allowing the vertices to perform a pre-computation at the beginning of their verification in a certification scheme 10 . We will use it so that each vertex 𝑢 will pre-compute the ECC-table 𝑇 𝐺 and its witnessed graph 𝐺 ≼𝑢 . Definition 4.3 (Local computation scheme). Let 𝑓 be a function taking as input a graph 𝐺 and a vertex 𝑢 of 𝐺. A local computation scheme for 𝑓 of size 𝑠 is a scheme where the prover gives certificates of size 𝑠 to the vertices, and each vertex either rejects, or outputs something. We also require the two following soundness conditions to be satisfied for every graph 𝐺 = (𝑉 , 𝐸):

(i) if no vertex rejects, then every vertex 𝑢 ∈ 𝑉 outputs 𝑓 (𝐺, 𝑢);

(ii) there exists a certificate assignment such that no vertex rejects.

Technical results

We now design local computation schemes to compute the ECC-table and the witnessed graphs, as stated in the following Theorems 4.4 and 4.5.

Theorem 4.4. There exists 𝑐 > 0 such that, for all 0 < 𝜀 < 1, there exists a local computation scheme for 𝑓 (𝐺, 𝑢) := 𝑇 𝐺 of size 𝑐 𝜀 • 𝑛 log 𝑛, if the vertices can see at distance 𝑘. Note that the output of the function 𝑓 in Theorem 4.4 does not depend on 𝑢, but only on 𝐺 and 𝜀.

Proof. Let 0 < 𝜀 < 1 and 𝑁 = ⌈ 1 𝜀 ⌉. Let us describe a local computation scheme for 𝑓 (𝐺, 𝑢) = 𝑇 𝐺 of size 𝑂 ( 𝑛 𝜀 log 𝑛). Certification. The certificates of the vertices consists of information stored in three fields, denoted by SpanningTree, Table and Components. The certificate is the same for all the vertices.

• The prover chooses a spanning tree T of 𝐺 and writes it in SpanningTree. More precisely: it writes the identifiers of all the vertices and of their parents in T using 𝑂 (𝑛 log 𝑛) bits. (i) First, every vertex checks that its certificate is the same as the certificates of its neighbors, and rejects if it is not the case.

(ii) To check the correctness of SpanningTree, every vertex checks if it is indeed a tree, and if each of its neighbors written in SpanningTree is indeed a neighbor in 𝐺. It rejects if it is not the case.

If no vertex rejects at this point, the spanning tree of 𝐺 written in SpanningTree is correct.

In particular, all the vertices know 𝑛, and the whole set of the identifiers of vertices in 𝐺. (iii) The next two steps of the verification consist in checking if the partition in ECC 𝑖 's written in 𝑇 𝐺 is correct. Every vertex 𝑢 checks that for all 𝑖 ∈ {1, . . . , 𝑁 }, and for all vertices 𝑣, 𝑤 ∈ 𝐻 𝑖 at distance at most 𝑘 -1 from 𝑢, we have If it is not the case, 𝑢 rejects.

Computation. If a vertex 𝑢 did not reject during the verification phase, it outputs Table . If no vertex rejects, we have Table = 𝑇 𝐺 (since both the partition in ECC 𝑖 's and the distances to the ECC 𝑖 's written in Table are correct). Moreover, if the prover gives the certificates as described above, no vertex will reject. Thus, the computation scheme is correct. □ Theorem 4.5. There exists 𝑐 > 0 such that, for all 0 < 𝜀 < 1, there exists a local computation scheme for 𝑓 (𝐺, 𝑢) := 𝐺 ≼𝑢 of size 𝑐 𝜀 • 𝑛 1+𝜀 • log 2 𝑛, if the vertices can see at distance 2. Proof of Theorem 4.5. Let 0 < 𝜀 < 1 and 𝑁 = ⌈ 1 𝜀 ⌉. We describe the local computation scheme. 11 Certification. Let us describe the certificates given by the prover to the vertices on correct instances. First, it gives to every vertex 𝑢 its certificate in the local computation scheme for 𝑇 𝐺 given by Theorem 4.4, which has size 𝑂 ( 𝑛 𝜀 log 𝑛). Then, the prover gives other additional information to 𝑢, denoted by Pieces(𝑢), which is the following. For every 𝑖 ∈ {1, . . . , 𝑁 }, the prover constructs the graph 𝐺 𝑖 obtained from 𝐺 by keeping only edges having at least one endpoint in 𝐿 𝑖 . Since each vertex in 𝐿 𝑖 has degree at most 𝑛 𝑖𝜀 , 𝐺 𝑖 has at most 𝑛 1+𝑖𝜀 edges. Then, the prover cuts the adjacency list of 𝐺 𝑖 (which has size 𝑛 1+𝑖𝜀 log 𝑛) in 𝑛 (𝑖 -1)𝜀 pieces of size 𝑛 1+𝜀 log 𝑛, and number them from 1 to 𝑛 (𝑖 -1)𝜀 . Finally, for every vertex 𝑢, it writes 3 log 𝑛 numbered pieces of 𝐺 𝑖 in Pieces(𝑢) in such a way: for each 𝑢 ∈ 𝐻 𝑖 , 𝑢 sees every piece 𝑃 of 𝐺 𝑖 in the certificate of at least one of its neighbors. Since each vertex 𝑢 ∈ 𝐻 𝑖 has degree at least 𝑛 (𝑖 -1)𝜀 , and since there are 𝑛 (𝑖 -1)𝜀 different pieces of 𝐺 𝑖 , this is possible (see Lemma 4.2 ). In total, since the prover does this for every 𝑖 ∈ {1, . . . , 𝑁 }, Pieces(𝑢) has size 𝑂 (𝑁 𝑛 1+𝜀 log 2 𝑛), so the size of the overall certificate is 𝑂 ( 𝑛 1+𝜀 𝜀 log 2 𝑛). Verification. The vertices perform the following verification procedure.

(i) First, each vertex applies the verification of the local computation scheme for 𝑇 𝐺 given by Theorem 4.4. (ii) To verify Pieces(𝑢), each vertex 𝑢 does the following: if it sees two numbered pieces 𝑃 ∈ Pieces(𝑣) and 𝑃 ′ ∈ Pieces(𝑤) for some 𝑣, 𝑤 at distance at most 𝑘 -1, such that 𝑃 and 𝑃 ′ are two pieces of 𝐺 𝑗 for some 𝑗 ∈ {1, . . . , 𝑁 } which are numbered the same, 𝑢 checks that these two pieces are indeed the same. If it is not the case, 𝑢 rejects. (iii) Finally, for every 𝑖 ∈ {1, . . . , 𝑁 }, each 𝑢 ∈ 𝑉 𝑖 does the following verification. For every 𝑗 ⩽ 𝑖, and for every numbered piece 𝑃 of 𝐺 𝑗 , 𝑢 checks if it sees 𝑃 in a certificate Pieces(𝑣) for some 𝑣 in its closed neighborhood. If it is not the case, 𝑢 rejects. And if 𝑢 sees that its own edges and non-edges are not correctly written in the piece 𝑃 of 𝐺 𝑖 where it should be, it rejects.

Computation. Let us describe the computation of every vertex 𝑢. If no vertex rejected at step (i), 𝑢 computed the ECC-table 𝑇 𝐺 . In particular, 𝑢 knows the partition of 𝐻 𝑖 in ECC 𝑖 's for every 𝑖 ∈ {1, . . . , 𝑁 }. So 𝑢 can compute the set 𝑉 ≼𝑢 . Claim 4.6. Let 𝑢, 𝑣 ∈ 𝑉 such that 𝑣 ≼ 𝑢. If no vertex rejected during the verification phase, then 𝑢 can compute all the edges and non-edges having 𝑣 as an endpoint.

Proof. Let 𝑖 ∈ {1, . . . , 𝑁 } such that 𝑣 ∈ 𝑉 𝑖 and 𝑢 ∈ 𝐻 𝑖 . Because of step (iii) of the verification, the vertex 𝑢 sees all the parts of 𝐺 𝑖 in its certificate or in the certificate of some of its neighbors. However, nothing ensures that these parts are correct. But thanks to step (ii), any two vertices in 𝐻 𝑖 at distance at most 2𝑘 -2 get the same pieces of 𝐺 𝑖 in their neighborhoods. So by transitivity, two vertices which are in the same ECC 𝑖 have the same pieces of 𝐺 𝑖 in their neighborhood. In particular, since 𝑢 and 𝑣 are in the same ECC 𝑖 , and since the edges and non-edges of 𝑣 are correctly written in the pieces which are in the closed neighborhood of 𝑣 (otherwise it would have rejected at step (iii)), then 𝑢 knows the edges and non-edges of 𝑣. □ Thus, if no vertex rejects in the verification phase, thanks to Claim 4.6, every vertex 𝑢 is able to reconstruct the graph 𝐺 ≼𝑢 thanks to the certificates Pieces it sees its neighborhood. Moreover, if the prover gives the certificates as described above, no vertex will reject. So the computation scheme is correct. □ Remark 4.7. Note that, with the certificates given in the certification scheme of Theorem 4.5, each vertex 𝑣 can also output the witnessed graph 𝐺 ≼𝑢 of any vertex 𝑢 at distance at most 𝑘 -1 from itself. Indeed, 𝑣 can see all the pieces of 𝐺 ≼𝑢 which are spread in certificates of vertices in 𝑁 [𝑢].

OVERVIEW OF THE FORBIDDEN SUBGRAPH CERTIFICATIONS

In this section, we sketch how we use the layered maps for forbidden subgraphs certification. All the formal proofs are in Section 6. We start with Theorem 1.10, that we have already discussed in the introduction, but now with the right notations, and more details. The statement is actually generalized in several ways later on, but it is good to discuss it first, to introduce the techniques one by one. Theorem 1.10. We can certify 𝑃 4𝑘 -1 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 3/2 log 2 𝑛).

What the prover does is the following: first, it uses the computation schemes of Theorems 4.4 and 4.5, with 𝜀 = 1 2 , that is 𝑁 = 2. Thus, 𝑉 is divided into 𝑉 1 (the set of vertices having degree less than √ 𝑛, the low-degree vertices) and 𝑉 2 (the set of vertices having degree higher than √ 𝑛, the high-degree vertices). Note that 𝐻 1 = 𝑉 so there is only one ECC 1 which is the whole set 𝑉 , and 𝐻 2 = 𝑉 2 . With the local certification schemes of Theorems 4.4 and 4.5, every vertex 𝑢 will compute its witnessed graph 𝐺 ≼𝑢 and the ECC-table 𝑇 𝐺 . Let us recall that 𝑇 𝐺 gives the partition of 𝑉 2 in ECC 2 's, and also the distance from every vertex of 𝑉 1 to its closest ECC 2 (if it is at most 𝑘 -1).

For every vertex 𝑣 ∈ 𝑉 1 and 𝑢 ∈ 𝑉 , we have 𝑣 ≼ 𝑢, hence 𝑢 computes 12 all the edges and non-edges of 𝑣. In other words: the adjacency of low-degree vertices is known by every vertex. In particular, if 𝐺 has an induced 𝑃 4𝑘 -1 which is made only of small-degree vertices in 𝐺, it is detected by every vertex. Note also that for all 𝑢, 𝑣 ∈ 𝑉 2 which are in the same ECC 2 , we have 𝑣 ≼ 𝑢, so 𝑢 knows all the edges and non-edges of 𝑣. In particular, if there is an induced 𝑃 4𝑘 -1 in 𝐺 containing high-degree vertices from only one ECC 2 , any vertex 𝑢 in this ECC 2 will detect it. So the difficult case is to detect an induced 𝑃 4𝑘 -1 in 𝐺 containing high-degree vertices from at least two different ECC 2 's. Using the fact that two distinct ECC 2 's are at distance at least 2𝑘 -1 from each other, we will see that it is in fact sufficient to consider the case of paths having big-degree vertices in exactly two different ECC 2 's.

To enable the vertices to detect the existence of paths of length 4𝑘 -1 going through exactly two distinct ECC 2 's, the prover will add some information in the certificates, which is the following. For each 𝑣 ∈ 𝑉 , if 𝑣 is close to an ECC 2 denoted by 𝐶 𝑣 , let us denote by 𝑃 𝑣 the longest induced path which starts at 𝑣 and has all its other vertices strictly closer from 𝐶 𝑣 than 𝑣. For every 𝑣 ∈ 𝑉 , the prover will give the length of 𝑃 𝑣 to all the vertices. Then, to verify the certificates, for every 𝐶 ∈ E 2 , every vertex 𝑢 ∈ 𝐶 will do the following: 𝑢 checks if there exists a path in 𝐺 ≼𝑢 which starts from 𝑢, ends in some vertex 𝑣 close to some ECC 2 𝐶 𝑣 ≠ 𝐶, and can be extended into a path of length 4𝑘 -1 using the path 𝑃 𝑣 . We prove that if a 𝑃 4𝑘 -1 path exists in the graph, touching two 𝐸𝐶𝐶 2 , then such a pair 𝑢, 𝑣 exists.

A first extension of this theorem is to certify any forbidden subgraph on 4𝑘 -1 vertices. Theorem 1.11. For every 𝑘 ⩾ 2, we can certify 𝐻 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 3/2 log 2 𝑛) for every 𝐻 of size at most 4𝑘 -1.

To prove this, we will have to certify more information than the lengths of longest paths 𝑃 𝑣 we had before. Informally speaking, for every vertex 𝑣, we will need to determine, for every possible node ℎ in 𝐻 , if 𝑣 can be node ℎ of a copy of 𝐻 that is in between two 𝐸𝐶𝐶 2 's.

Then we push the technique to get quasi-linear size certificates. Theorem 1.12. For every 𝑘 ⩾ 2, we can certify 𝑃 3𝑘 -1 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 log 3 𝑛).

To prove this, we will use the whole power of the witnessed graphs and layered maps since we will use it with an arbitrary number of layers (while the previous bounds only used two layers). Doing it introduces technicalities that did not appear in the previous cases (and that explain why we were only able to get 𝑃 3𝑘 -freeness instead of 𝑃 4𝑘 -1 -freeness).

Finally, we achieve to increase the length of the path, keeping the same size as in Theorem 1.10. Theorem 1.13. For every 𝑘 ⩾ 2, we can certify 𝑃 ⌈ 14 3 𝑘⌉ -1 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 3/2 log 2 𝑛).

Again the proof is inspired by the proof of Theorem 1.10. However, in order to get the result, we need to add different information in the certificate of each vertex. Indeed, so far, the certificate where almost global in the sense that, except in order to certify the graph 𝐺 ≼𝑢 for every 𝑢 in Theorem 4.5, the certificate given to vertices where the same. In that proof, we need to add local certificate on each node and then we will have to be more careful on which vertex can detect the existence of a path if a path exists. Very informally speaking, the information we will be able to store is, for every vertex 𝑣, what happens if only two vertices of a path belong to 𝐶 (𝑑) (assuming that 𝑣 is in 𝐶 (𝑑)).

FORMAL PROOFS OF THE FORBIDDEN SUBGRAPH CERTIFICATIONS

In this section, we prove all our upper bounds: Theorem 1.10, Theorem 1.11, Theorem 1.12 and Theorem 1.13. These are presented by increasing level of technicality.

Upper bound for 𝑃

4𝑘 -1 in Õ (𝑛 3/2 )
Theorem 1.10. We can certify 𝑃 4𝑘 -1 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 3/2 log 2 𝑛).

Proof of Theorem 1.10. Let 𝐺 = (𝑉 , 𝐸) be an 𝑛-vertex graph.

Certification. The certification of the prover is the following. First, it gives to each vertex its certificates in the local computation schemes given by Theorems 4.4 and 4.5, with 𝜀 = 1 2 , so that each vertex 𝑢 can compute 𝑇 𝐺 and 𝐺 ≼𝑢 . These certificates have size 𝑂 (𝑛 3/2 log 2 𝑛).

Then, the prover adds some additional information in the certificates, in another field, which will be identical in the certificates of all the vertices. We will denote this field by LongestPaths, and it is defined as follows (note that it has size 𝑂 (𝑛 log 𝑛)). Definition 6.1 (𝑃 𝑣 , LongestPaths). For every vertex 𝑣 ∈ 𝑉 1 such that 𝑇 𝐺 [𝑣, 2] = (𝑖𝑑 (𝐶 𝑣 ), 𝑑 𝑣 ), let 𝑃 𝑣 be a longest induced path starting from 𝑣 and having all its other vertices in 0⩽𝑑 <𝑑 𝑣 𝐶 𝑣 (𝑑), and let ℓ (𝑃 𝑣 ) be its length. We define LongestPaths as being the array indexed by the identifiers of the vertices, such that LongestPaths[𝑣] = ℓ (𝑃 𝑣 ) for every 𝑣 ∈ 𝐶 ∈ E 2 1⩽𝑑 ⩽𝑘 -1 𝐶 (𝑑).

Verification. We define for each 𝑚 ⩾ 1 a protocol we call 𝑚-pathcheck below. (We define the 𝑚-pathcheck for arbitrary 𝑚, because we will use it again when we prove Theorem 1.13.) In our verification phase each vertex runs the 𝑚-pathcheck for 𝑚 = 4𝑘 -1. Definition 6.2 (𝑚-pathcheck). Each vertex 𝑢 ∈ 𝑉 takes as input its view at distance 𝑘 (with the certificates described above) and peforms the following steps:

(i) First, 𝑢 applies the verification of the local computation schemes of Theorems 5.

Properties of the 𝑚-pathcheck. We begin with some observations about the 𝑚-pathcheck. Lemma 6.3. Suppose 𝐺 contains an induced path 𝑃 on 𝑚 vertices. If there is at most one 𝐶 ∈ E 2 such that |𝐶 ∩ 𝑃 | ⩾ 2, some vertex rejects during the 𝑚-pathcheck.

Proof. We may assume that no vertex rejects during the first three steps of the 𝑚-pathcheck. If 𝑃 ⊆ 𝑉 1 , then every vertex 𝑢 ∈ 𝑃 rejects at step (iv). Else, we have 𝑃 ∩ 𝑉 2 ≠ ∅, and let 𝐶 ∈ E 2 such that |𝑃 ∩ 𝐶 | is maximized. By assumption, for every 𝐶 ′ ∈ E 2 such that 𝐶 ′ ≠ 𝐶, we have |𝑃 ∩ 𝐶 ′ | ⩽ 1, so every 𝑢 ∈ 𝐶 rejects at step (iv). □ Lemma 6.4. Suppose 𝐺 contains an induced path 𝑃 on 𝑚 vertices with the following properties:

• there are exactly two distinct ECC 2 's 𝐶 𝑢 , 𝐶 𝑣 ∈ E 2 which contain vertices of 𝑃 • for some 𝑑 ∈ {1, 2, . . . , 𝑘 -1}, there is a unique vertex 𝑣 at distance exactly 𝑑 from 𝐶 𝑣 Then some vertex rejects during the 𝑚-pathcheck.

Proof. As depicted in Figure 5, we can decompose 𝑃 in two consecutive parts 𝑃 start , 𝑃 end such that:

• 𝑃 start ∩ 𝑃 end = {𝑣 }; • 𝑃 start ⊆ 𝐶 𝑢 ∪ 𝑉 1 ; • 𝑃 end \ {𝑣 } ⊆ 0⩽𝑑 <𝑑 𝑣 𝐶 𝑣 (𝑑).
We may assume that no vertex rejects during the first four steps of the 𝑚-pathcheck. We claim that every 𝑢 ∈ 𝑃 ∩ 𝐶 𝑢 will reject at step (v). Correctness. Let us show that this certification scheme is correct. Assume first by contradiction that 𝐺 contains an induced path 𝑃 of length 4𝑘 -1. Let us show that for every assignment of certificates, at least one vertex rejects. If no vertex rejects at step (i) of the verification, then every vertex 𝑢 knows its witnessed graph 𝐺 ≼𝑢 and the ECC-table 𝑇 𝐺 (note that 𝑢 also knows 𝑉 ≼𝑢 , because it can be computed directly from 𝑇 𝐺 ). If no vertex rejects in step (iii), then LongestPaths is also correct. Then, let us prove the two following Claims 6.5 and 6.3. Proof. This simply follows from the fact that 𝑃 has length 4𝑘 -1, and two different ECC 2 's are at distance at least 2𝑘 -1. □ Applying Claim 6.5 and Lemma 6.3, we can assume that there are exactly two different ECC 2 's which intersect 𝑃, and both on at least two vertices. Let us denote them by 𝐶 𝑢 and 𝐶 𝑣 . Since 𝑃 is a path going through 𝐶 𝑢 and 𝐶 𝑣 which are at distance at least 2𝑘 -1 from each other, for all 𝑑 ∈ {1, . . . , 𝑘 -1}, we have 𝑃 ∩ 𝐶 𝑢 (𝑑) ≠ ∅, and 𝑃 ∩ 𝐶 𝑣 (𝑑) ≠ ∅. Moreover, since 𝑃 has length 4𝑘 -1, and since 𝑃 ∩ 𝐶 𝑢 (0), 𝑃 ∩ 𝐶 𝑣 (0) both contain at least two vertices, there exists a set 𝑃 ∩ 𝐶 𝑢 (𝑑) or 𝑃 ∩𝐶 𝑣 (𝑑) which contains only one vertex, for some 𝑑 ∈ {1, . . . , 𝑘 -1}. Hence, by applying Lemma 6.4 for 𝑚 = 4𝑘 -1 we obtain that a some vertex rejects during our verification protocol as desired.

Conversely, assume that 𝐺 does not have an induced path of length 4𝑘 -1. Let us show that there exists an assignment of the certificates such that every vertex accepts. This assignment is the following one: the prover attributes the certificates such that no vertex reject in the local computation schemes of Theorems 4.4 and 4.5, and gives the correct value of LongestPaths to every vertex. With such a certificate, it is straightforward that a vertex can not reject at steps (i), (ii) and (iii).

Assume by contradiction that a vertex 𝑢 rejects at step (iv). Then, there exists an induced path 𝑃 of length 4𝑘 -1 in 𝐺 ≼𝑢 , such that the vertices in 𝑃 \ 𝑉 ≼𝑢 are in distinct ECC 2 's. Since 𝐺 does not have an induced path of length 4𝑘 -1, 𝑃 is not induced in 𝐺. It implies that there are two vertices of 𝑃 linked by an edge in 𝐺, an a non-edge in 𝐺 ≼𝑢 . Thus, these two vertices are in 𝑉 \ 𝑉 ≼𝑢 (because edges having an endpoint in 𝑉 ≼𝑢 are in 𝐺 ≼𝑢 ). So by definition of step (iv), these two vertices are in distinct ECC 2 's. In particular, they can not be neighbors in 𝐺, which is a contradiction.

Finally, assume by contradiction that a vertex 𝑢 rejects at step (v). It means that there exists an induced path 𝑃 start in 𝐺 ≼𝑢 , included in 𝑉 ≼𝑢 , ending in some vertex 𝑣 satisfying the conditions of step (v). Since 𝑃 start ⊆ 𝑉 ≼𝑢 , it is also induced in 𝐺. Moreover, there exists an induced path 𝑃 𝑣 in 𝐺 of length ℓ (𝑃 𝑣 ) starting in 𝑣 and having all its other vertices in 𝑑 <𝑑 𝑣 𝐶 𝑣 (𝑑). Since 𝑣 is the only vertex in 𝑃 start ∩ ( 𝑑 ⩽𝑑 𝑣 𝐶 𝑣 (𝑑)), then the concatenation of 𝑃 start and 𝑃 𝑣 is still an induced path in 𝐺. Moreover, it has length ℓ (𝑃 start ) + ℓ (𝑃 𝑣 ) -1 ⩾ 4𝑘 -1. It is a contradiction. Thus, no vertex rejects at step (v), so all the vertices accept at step (vi), which concludes the proof. □ 6.2 Upper bound for general graphs of size 4𝑘 -1 in Õ (𝑛 3/2 ) Theorem 1.11. For every 𝑘 ⩾ 2, we can certify 𝐻 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 3/2 log 2 𝑛) for every 𝐻 of size at most 4𝑘 -1.

Before proving Theorem 1.11, let us give some informal intuition on the proof. The general idea is the same as in the proof of Theorem 1.10: first, the prover uses the local computation schemes of Theorems 4.4 and 4.5 with 𝜀 = 1 2 (such that each vertex 𝑢 computes 𝐺 ≼𝑢 and 𝑇 𝐺 ), and then it adds some additional information in the certificates. The main difference is the following one. Theorem 1.10 is the particular case where the graph 𝐻 is a path. In this case, the information the prover adds in the certificates is, for each vertex 𝑣 ∈ 𝑉 close to some 𝐶 𝑣 ∈ E 2 , the length of the longest induced path 𝑃 𝑣 starting from 𝑣 and having all its other vertices closer from 𝐶 𝑣 than 𝑣. This enables a vertex 𝑢 in an ECC 2 𝐶 𝑢 ≠ 𝐶 𝑣 to check, for every induced path 𝑃 in 𝐺 ≼𝑢 , if it can be extended into a path of length 4𝑘 -1 using 𝑃 𝑣 . Here, for an arbitrary graph 𝐻 , we generalize it: the information the prover will add is, intuitively, for each vertex 𝑣 close from an ECC 2 𝐶 𝑣 , and for every induced subgraph 𝐻 ′ of 𝐻 , if 𝐻 ′ is induced in the part of 𝐺 consisting in 𝑣 and all the vertices closer from 𝐶 𝑣 than 𝑣. With this information, every vertex 𝑢 in an ECC 2 𝐶 𝑢 ≠ 𝐶 𝑣 will be able to detect if some induced graph in 𝐺 ≼𝑢 can be extended into 𝐻 using 𝐻 ′ .

Pointed graphs. Let us introduce some definitions about pointed graphs that will be useful in the proof of Theorem 1.11. A pointed graph is a tuple (𝐻, 𝑆) where 𝐻 is a graph and 𝑆 ⊆ 𝑉 (𝐻 ) is a set of pointed vertices. If (𝐻 1 , 𝑆 1 ), (𝐻 2 , 𝑆 2 ) are two pointed graphs, their disjoint union is the pointed graph (𝐻 1 ∪ 𝐻 2 , 𝑆 1 ∪ 𝑆 2 ), where 𝐻 1 ∪ 𝐻 2 is the graph obtained by taking a copy of 𝐻 1 and a copy of 𝐻 2 , and no edge between them. Finally, let 𝐺 be a graph, 𝐻 an induced subgraph of 𝐺 and 𝑆 ⊆ 𝑉 (𝐻 ). The complement of (𝐻, 𝑆) in 𝐺 is the pointed subgraph (𝐻, 𝑆) where 𝐻 is the subgraph of 𝐺 induced by (𝑉 (𝐺) \ 𝑉 (𝐻 )) ∪ 𝑆.

Proof of Theorem 1.11. Let 𝐻 be a graph with 4𝑘 -1 vertices. Let us describe a certification scheme for 𝐻 -free graphs with certificates of size 𝑂 (𝑘 • 2 4𝑘 • 𝑛 + 𝑛 3/2 log 2 𝑛), by looking at distance 𝑘.

Certification. The certification of the prover is the following. First, it gives to each vertex its certificates in the local computation schemes given by Theorems 4.4 and 4.5, with 𝜀 = 1 2 . This part of the certificate has size 𝑂 (𝑛 3/2 log 2 𝑛).

Then, the prover adds some additional information in the certificates, in a field which will be identical in the certificates of all the vertices. We will denote this field by HTable, and it is defined as follows. Let P (𝐻 ) be the set containing all the pointed graphs (𝐻 ′ , {ℎ}), where ℎ ∈ 𝑉 (𝐻 ), and 𝐻 ′ is a subgraph of 𝐻 induced by {ℎ} and an union of connected components of 𝐻 \ {ℎ}. An example is shown on Figure 6. The field HTable contains a table which has at most 𝑛 rows and (4𝑘 -1) • 2 4𝑘 -1 columns. The rows are indexed by the identifier of the vertices which are at distance at most 𝑘 -1 from 𝑉 2 , and the columns are indexed by the pointed graphs (𝐻 ′ , {ℎ}) ∈ P (𝐻 ). Let 𝑣 ∈ 𝑉 , such that 𝑣 is at distance 𝑑 𝑣 ⩽ 𝑘 -1 from some 𝐶 𝑣 ∈ E 2 . HTable[𝑣, (𝐻 ′ , {ℎ})] is equal to 1 if 𝐻 ′ is an induced subgraph of 𝑑 ⩽𝑑 𝑣 𝐶 𝑣 (𝑑), where all the vertices in 𝐻 ′ \ {ℎ} are mapped in 𝑑 <𝑑 𝑣 𝐶 𝑣 (𝑑), and ℎ is mapped to 𝑣. Otherwise, HTable[𝑣, (𝐻, {ℎ})] is equal to 0. An example with the pointed graph 𝐻 ′ of Figure 6 is shown on Figure 7. Since the table HTable has at most 𝑛 rows and (4𝑘 -1) •2 4𝑘 -1 columns, with each entry of constant size, its has size 𝑂 (𝑘 • 2 4𝑘 • 𝑛). The overall size of the certificate is thus 𝑂 (𝑘 • 2 4𝑘 • 𝑛 + 𝑛 3/2 log 2 𝑛).

Verification. The verification of each vertex 𝑢 ∈ 𝑉 consists in the following.

(i) First, 𝑢 applies the verification of the local computation schemes of Theorems 4.4 and 4.5.

If no vertex rejects during this first verification phase, then every vertex 𝑢 computed 𝑇 𝐺 and 𝐺 ≼𝑢 . (ii) Then, 𝑢 checks that HTable is the same in its certificate and in the certificate of all its neighbors. If it is not the case, 𝑢 rejects. If no vertex rejects, HTable is the same in the certificates of all the vertices in 𝐺. The next step will consist in checking its correctness. (iii) If 𝑢 ∈ 𝑉 2 , it does the following. Let 𝐶 𝑢 be its ECC 2 . We have (ix) If 𝑢 did not reject in the previous steps, it accepts.

Correctness. Let us prove that this certification scheme is correct. First let us assume for a contradiction, that 𝐺 contains an induced path 𝑃 of length 𝑚 and that every vertex accepts. Using the 𝑚-pathcheck, every vertex 𝑢 can correctly compute 𝑇 𝐺 , 𝐺 ≼𝑢 , and knows that the values of LongestPaths and LongestConstrainedPath(𝑢) written by the prover in the certificates are correct. Then, let us prove the following Claims 6.10, 6.12 and 6.13. Claim 6.10. There are three subpaths 𝑃 1 , 𝑃 2 , 𝑃 3 of 𝑃 such that 𝑃 = 𝑃 1 ∪𝑃 2 ∪𝑃 3 and for each 𝑖 ∈ {1, 2, 3} there is a 𝐶 𝑖 ∈ E 2 such that every vertex of 𝑉 (𝑃 𝑖 ) ⊆ 𝐶 𝑖 ∪ 𝑉 1 .

Proof. This simply follows from the fact that 𝑃 has length 𝑚 < 14 3 𝑘 and that two distinct ECC 2 's are at distance at least 2𝑘 from each other by definition of extended connected component.

■ Proof. Assume that there are exactly three 𝐶 ∈ E 2 such that 𝑃 ∩ 𝐶 ≠ ∅. Let us denote these three ECC 2 's by 𝐶 1 , 𝐶 2 , 𝐶 3 . By Claim 6.12, we can can also assume that 𝑃 has at least 5 vertices in 𝐶 1 ∪ 𝐶 2 ∪ 𝐶 3 . Without loss of generality, there is a subpath of 𝑃 passing through 𝐶 1 , 𝐶 3 , 𝐶 2 , in that order. For 𝑥 ∈ {1, 2, 3}, let 𝐵 𝑥 denote the set of vertices of 𝑉 (𝑃) in 1⩽𝑑 ⩽𝑘 -1 𝐶 𝑥 (𝑑).

It
Let 𝑖 ∈ {1, 2}. From the definition of ECC, there must be a vertex at distance at 𝑘 -1 from 𝐶 𝑖 in 𝐵 𝑖 . Since 𝑃 contains a vertex of 𝐶 𝑖 it follows that for each 𝑑 ∈ {1, 2, . . . , 𝑘 -1} there is some vertex 𝑏 ∈ 𝐵 𝑖 at distance exactly 𝑑 from 𝐶 𝑖 . Hence, it follows from (1) that there exists some 𝑑 𝑖 ∈ {1, . . . , 𝑘 -1} such that |𝑃 ∩ 𝐶 𝑖 (𝑑 𝑖 )| = 1. Let 𝑣 𝑖 denote the unique element of 𝑃 ∩ 𝐶 𝑖 (𝑑 𝑖 ). Let 𝑃 start denote the 𝑣 1 𝑣 2 -path of 𝑃.

Let 𝑢 ∈ 𝐶 3 be arbitrary. We will show that 𝑢 rejects at step (vii). By definition of ECC 2 , the only vertices of 𝑉 2 in 𝑃 start are contained in 𝐶 3 . So in particular, 𝑉 (𝑃 start ) ⊆ 𝑃 ≼𝑢 Hence, 𝑢 will consider 𝑃 start in step (vii) and it will reject if ℓ (𝑃 start ) + (LongestPaths[𝑣 1 ] -1) + (LongestPaths[𝑣 2 ] -1) ⩾ 𝑚.

By definition, there the graph obtained from 𝑃 by deleting all vertices of 𝑃 start except for 𝑣 1 , 𝑣 2 consists of two paths 𝑃 1 , 𝑃 2 such that 𝑣 1 is an end of 𝑃 1 and 𝑣 2 is an end of 𝑃 2 . Let 𝑖 ∈ {1, 2}. By Claim 6.10 we have that 𝑃 𝑖 ⊆ 𝑉 𝑖 ∪ 𝐶 𝑖 . Since 𝑃 𝑖 contains a vertex of 𝐶 𝑖 , by the definition of distance, there can be no vertex 𝑉 (𝑃 𝑖 ) at distance strictly greater than 𝑑 𝑖 from 𝑣 𝑖 . It follows that 𝑉 (𝑃 𝑖 ) \ {𝑣 𝑖 } ⊆ 0⩽𝑑 <𝑑 𝑖 𝐶 𝑖 (𝑑). Hence by definition, LongestPaths(𝑣 𝑖 ) ⩾ |𝑉 (𝑃 𝑖 )| -1.

Since 𝑃 = 𝑃 1 ∪𝑃 2 ∪𝑃 3 , it follows that ℓ (𝑃 start )+(LongestPaths[𝑣 1 ]-1)+(LongestPaths[𝑣 2 ]-1) ⩾ 𝑚 and therefore 𝑢 rejects in step (vii). □ Applying Claims 6.10, 6.12 and 6.13, we can assume that there exactly two ECC 2 's which intersect 𝑃, both on at least two vertices. Let us denote these two ECC 2 's by 𝐶 𝑢 and 𝐶 𝑣 .

1 2𝑘Fig. 1 .

 11 Fig. 1. The graph 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ). Each blob is a clique on 𝑛 vertices. The double thick edges represent the graphs 𝐻 and 𝐻 ′ . The other double edges represent the matchings. The double dashed edges represent the antimatchings.

Fig. 2 .

 2 Fig. 2. The case described in (ii) of Claim 3.4.

  The second case (𝑥 ′ ∉ {𝑥, 𝑦}).

Fig. 3 . 1 𝑤Fig. 4 .

 314 Fig. 3. The two cases described at the end of the proof of Lemma 3.3....

Claim 3 . 5 .

 35 For each ℓ ∈ {1, 2, . . . , 2𝑘 } the vertices of 𝑃 in 𝐾 0 ℓ ∪ 𝐾 1 ℓ are exactly 𝐾 0 ℓ [𝑖], 𝐾 1 ℓ [ 𝑗] or they are exactly 𝐾 0 ℓ [ 𝑗], 𝐾 1 ℓ [𝑖].

  By definition, |𝑉 (𝑃 start )| = 𝑚 -|𝑉 (𝑃 end )| -1. Let 𝑃 𝑣 denote the the longest induced path starting at 𝑣 and having all its other vertices strictly closer from 𝐶 𝑣 than 𝑣. Hence, |𝑉 (𝑃 𝑣 )| ⩾ |𝑉 (𝑃 end )|, so ℓ (𝑃 start ) + LongestPaths[𝑣] ⩾ 𝑚. 𝑃 start is an induced path of 𝐺 ≼𝑢 , included in 𝑉 ≼𝑢 , which satisfies the conditions making 𝑢 reject at step (v).□

Fig. 6 .Fig. 7 .

 67 Fig.6. An example of a graph 𝐻 and a pointed graph (𝐻 ′ , {ℎ}) ∈ P (𝐻 ).

Fig. 12 .Fig. 13 .

 1213 Fig. 12. The case making 𝑢 reject at step (vii) in the certification scheme of Theorem 1.13

  Since any two distinct ECC 2 's are at distance at least 2𝑘-1 from each other, |𝐵 1 |, |𝐵 2 | ⩾ 𝑘 -1 and |𝐵 3 | ⩾ 2𝑘 -2. By definition of ECC, 𝐵 1 , 𝐵 2 , 𝐵 3 are pairwise disjoint. By Claim 6.12, we can can also assume that 𝑃 has at least 5 vertices in 𝐶 1 ∪ 𝐶 2 ∪ 𝐶 3 . And by definition, 𝐶 1 ∪ 𝐶 2 ∪ 𝐶 3 is disjoint from 𝐵 1 ∪ 𝐵 2 ∪ 𝐵 3 . By definition, |𝑉 (𝑃)| = 𝑚 ⩽ 14 3 𝑘. So by combining these observations we obtain: |𝐵 1 |, |𝐵 2 | ⩽ 𝑉 (𝑃) -3𝑘+3 -5 < 2𝑘 -2

Claim 6 . 14 .

 614 For all 𝑑 ∈ {1, . . . , 𝑘 -1}, we have |𝑃 ∩ 𝐶 𝑣 (𝑑)| ⩾ 2, and similarly |𝑃 ∩ 𝐶 𝑢 (𝑑)| ⩾ 2.

Table 1

 1

. Bounds for induced paths verification when vertices can see at distance 𝑘 ⩾ 2.

  1 𝑗 [𝑖])} 1⩽𝑖 ⩽𝑛 .• For every 𝑗 ∈ {1, . . . , 2𝑘 -1} and for every pair of cliques 𝐾, 𝐾 ′ with 𝐾 ∈ {𝐾 0 𝑗 , 𝐾 1 𝑗 }, 𝐾 ′ ∈ {𝐾 0 𝑗+1 , 𝐾 1 𝑗+1 }, we put the antimatching defined by the complement of {(𝐾 [𝑖], 𝐾 ′ [𝑖])} 1⩽𝑖 ⩽𝑛 between 𝐾 and 𝐾 ′ (that is, all the edges but the matching {(𝐾 [𝑖], 𝐾 ′ [𝑖])} 1⩽𝑖 ⩽𝑛 ). Finally, if 𝑇 = 𝑃 4𝑘+3 , we add 3 more vertices 𝑣 0 , 𝑣 1 , 𝑤 in the following way. The vertex 𝑣 0 (resp. 𝑣 1 ) is complete to 𝐾 0 1 (resp. 𝐾 1 1 ). The vertex 𝑤 is complete to 𝐾 0 2𝑘 and 𝐾 1 2𝑘 . Otherwise, we choose a path 𝑃 of length 4𝑘 in 𝑇 containing no leaf, label its vertices by 𝑣 0 1 , . . . , 𝑣 0 2𝑘 , 𝑤, 𝑣 1 2𝑘 , . . . , 𝑣 1 1 , and for each connected component 𝐶 of 𝑇 \ 𝑃 adjacent with vertex 𝑣 𝑏 𝑎 , we create a copy of 𝐶 in 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ) where the vertex adjacent with 𝑣 𝑏 𝑎 becomes complete to 𝐾 𝑏 𝑎 . Vertices in this copy are called pending vertices of 𝐾 𝑏 𝑎 . We also add a copy of the connected component of 𝑤 in 𝑇 \ 𝐸 (𝑃), and add all edges between 𝑤 and 𝐾 0 2𝑘 ∪ 𝐾 1 2𝑘 . Note that applying the latter construction to 𝑃 4𝑘+3 yields the former graph, hence we may use 𝐺 𝑘,𝑛 (𝐻, 𝐻 ′ ) in both cases.

  Claim 3.4. 𝑇 has at most two vertices in each clique and (i) If 𝑇 has two vertices in a clique 𝐾, then for all the cliques 𝐾 ′ antimatched with 𝐾, 𝑇 has at most one vertex in 𝐾 ′ , and (ii) If 𝑇 has two vertices in a clique 𝐾 𝑖 𝑗 , then 𝑇 has at most one vertex in 𝐾 1-𝑖 𝑗 . Proof. Since 𝑇 is triangle-free, it contains at most two vertices in each clique. Suppose there is a clique 𝐾 := 𝐾 𝑖 𝑗 and two distinct integers 𝑥, 𝑦 ∈ {1, 2, . . . , 𝑛} such that the vertices 𝐾 [𝑥] and 𝐾 [𝑦] are both in 𝑇 . We prove (i) and (ii) separately:

• For (i), let 𝐾 ′ be a clique antimatched to 𝐾. For each 𝑧 ∈ {1, 2, . . . , 𝑛}, 𝐾 ′ [𝑧] is adjacent to 𝐾 [𝑥] (if 𝑧 ≠ 𝑥) or to 𝐾 [𝑦] (if 𝑧 ≠ 𝑦). Thus, if there were at least two vertices in 𝑇 ∩ 𝐾 ′ , 𝑇 would have either a 𝐶 3 or a 𝐶 4 as a subgraph, which is a contradiction with 𝑇 being a tree.

  table. Let 𝑇 𝐺 be the following table, with 𝑛 rows and 𝑁 columns, called the ECC-table of 𝐺. The rows are indexed by the identifiers of the vertices, and the columns by {1, . . . , 𝑁 }. Let 𝑢 ∈ 𝑉 and 𝑖 ∈ {1, . . . , 𝑁 }. Let us describe the entry 𝑇 𝐺 [𝑢, 𝑖]. • If 𝑢 is at distance at most 𝑘 -1 from some ECC 𝑖 𝐶 𝑢 , we set 𝑇 𝐺 [𝑢, 𝑖] as (𝑖𝑑 (𝐶 𝑢 ), 𝑑 𝑢 ) where 𝑑 𝑢 is the distance from 𝑢 to 𝐶 𝑢 . Note that 𝑢 ∈ 𝐻 𝑖 if and only if 𝑑 𝑢 = 0. • Otherwise, we set 𝑇 𝐺 [𝑢, 𝑖] = ⊥.

  • In Table, the prover writes the table 𝑇 𝐺 . Since it has 𝑛 rows, 𝑁 columns, and 𝑂 (log 𝑛) bits per cell, it has size 𝑂 (𝑁 𝑛 log 𝑛). • In Components, the prover gives information to the nodes to check the correctness of the partition in 𝐸𝐶𝐶 𝑖 's written in Table. For each 𝑖 ∈ {1, . . . , 𝑁 }, and for each 𝐶 ∈ E 𝑖 , the prover constructs the graph 𝐺 𝐶 , where the vertices of 𝐺 𝐶 are the vertices of 𝐶, and there is an edge between two vertices in 𝐺 𝐶 if and only if they are at distance at most 2𝑘 -2 in 𝐺. By definition of an ECC 𝑖 , 𝐺 𝐶 is connected. Then, the prover chooses a spanning tree T 𝐶 of 𝐺 𝐶 and writes its structure in Components, with the identifier of the corresponding vertices. For each edge (𝑢, 𝑣) in T 𝐶 , there exists a vertex 𝑤 ∈ 𝑉 at distance at most 𝑘 -1 from both 𝑢 and 𝑣 in 𝐺. The prover labels the edge (𝑢, 𝑣) in T 𝐶 by the identifier of 𝑤. For a given 𝐶 ∈ E 𝑖 , 𝑂 (|𝐶 | log 𝑛) bits are required. In total, since the prover does this for each 𝐶 ∈ E 𝑖 and every 𝑖 ∈ {1, . . . , 𝑁 }, it uses 𝑂 (𝑁 𝑛 log 𝑛) bits. Since 𝑁 = ⌈ 1 𝜀 ⌉, the overall size of the certificate is thus 𝑂 ( 𝑛 𝜀 log 𝑛). Verification. The vertices perform the following verification procedure.

  Table[𝑣, 𝑖] = Table[𝑤, 𝑖], and if this common value is of the form (𝑖𝑑 (𝐶), 0). If it is not the case, 𝑢 rejects. If no vertex rejects at this point, then for all 𝑖 ∈ {1, . . . , 𝑁 } and for every pair of vertices 𝑣, 𝑤 ∈ 𝐻 𝑖 which are at distance at most 2𝑘 -2, 𝑣 and 𝑤 are written to be in the same ECC 𝑖 in Table. By transitivity: if two vertices are in the same ECC 𝑖 in 𝐺, then they appear in the same ECC 𝑖 in Table. (iv) Every vertex 𝑢 ∈ 𝑉 determines the index 𝑗 ∈ {1, . . . , 𝑁 } such that 𝑢 ∈ 𝑉 𝑗 . For every 𝑖 ⩽ 𝑗, 𝑢 does the following. We have 𝑢 ∈ 𝐻 𝑖 . Let 𝐶 𝑢 ∈ E 𝑖 be the ECC 𝑖 of 𝑢. The vertex 𝑢 checks that T 𝐶 𝑢 written in Components is indeed a tree. Moreover, for each edge (𝑢, 𝑣) in T 𝐶 𝑢 labeled with the identifier of a vertex 𝑤, 𝑢 checks if it sees indeed 𝑤 at distance at most 𝑘 -1 (and rejects if it is not the case).

If no vertex rejects at this point, for all vertices 𝑢, 𝑣 ∈ 𝑉 , if Table

[

𝑢, 𝑖] = Table[𝑣, 𝑖]

and if this value is of the form (𝑖𝑑 (𝐶), 0), then 𝑢 and 𝑣 are indeed two vertices of 𝐻 𝑖 which are in the same ECC 𝑖 (indeed, T 𝐶 is connected, so there exists a path from 𝑢 to 𝑣 in T 𝐶 , which corresponds to a path in 𝐺 which does not have 2𝑘 -1 consecutive vertices in 𝐿 𝑖 -1 ). Thus, together with step (iii) of the verification, the partition in ECC 𝑖 's written in Table is correct. (v) The next step of the verification consists in checking if the distances written in Table are also correct. To do so, every vertex 𝑢 does the following. For each 𝑖 ∈ {1, . . . , 𝑛}, if 𝑢 ∉ 𝐻 𝑖 , 𝑢 checks that Table[𝑢, 𝑖] = ⊥ if and only if 𝑢 does not see any vertex of 𝐻 𝑖 at distance at most 𝑘 -1. And if 𝑢 sees vertices in some 𝐶 𝑢 ∈ E 𝑖 at distance 𝑑 𝑢 , 𝑢 checks that Table[𝑢, 𝑖] = (𝑖𝑑 (𝐶 𝑢 ), 𝑑 𝑢 ).

  4.4 and 4.5. If no vertex rejects during this verification phase, then every vertex 𝑢 computed 𝑇 𝐺 and 𝐺 ≼𝑢 . (ii) Then, 𝑢 checks that LongestPaths is the same in its certificate and the certificates of all its neighbors. If it is not the case, 𝑢 rejects. If no vertex rejects at this point, then LongestPaths is the same in the certificates of all vertices in 𝐺. (iii) Suppose 𝑢 ∈ 𝑉 2 . Let 𝐶 𝑢 denote the ECC 2 containing 𝑢. By definition, of ECC and 𝑉 ≼𝑢 , 1⩽𝑑 ⩽𝑘 -1 𝐶 𝑢 (𝑑) ⊆ 𝑉 1 ⊆ 𝑉 ≼𝑢 Since 𝑢 computed 𝐺 ≼𝑢 in Step (i), for each 𝑣 ∈ 1⩽𝑑 ⩽𝑘 -1 𝐶 𝑢 (𝑑), 𝑢 can compute the length of the path 𝑃 𝑣 , and check if it is correctly written in LongestPaths. If this verification fails, 𝑢 rejects. If no vertex rejects at this point, then LongestPaths is correct in the certificate of every vertex. We may assume no vertex has rejected during steps (i) to (iii), and thus every vertex 𝑢 has access to a (correct) 𝑇 𝐺 , 𝐺 ≼𝑢 and LongestPaths. (iv) If 𝐺 ≼𝑢 has an induced path 𝑃 on 𝑚 vertices, such that all the vertices in 𝑃 \ 𝑉 ≼𝑢 are in distinct ECC 2 's, then 𝑢 rejects. (v) If 𝑢 ∈ 𝑉 2 , let us denote by 𝐶 𝑢 its ECC 2 . By definition, 𝑉 ≼𝑢 = 𝑉 1 ∪ 𝐶 𝑢 so by step (i) 𝑢 knows the graph induced by 𝑉 1 ∪ 𝐶 𝑢 . It rejects if it sees an induced path 𝑃 start in 𝐺 [𝐶 𝑢 ∪ 𝑉 1 ] satisfying all of the following: • 𝑃 start contains at least one vertex from 𝐶 𝑢 • 𝑃 start ends in a vertex 𝑣, such that 𝑇 𝐺 [𝑣, 2] = (𝑖𝑑 (𝐶 𝑣 ), 𝑑 𝑣 ) with 𝑖𝑑 (𝐶 𝑣 ) ≠ 𝑖𝑑 (𝐶 𝑢 ). This implies that 𝑣 is at distance 𝑑 𝑣 ⩽ 𝑘 -1 from 𝐶 𝑣 ∈ E 2 \ 𝐶 𝑢 . (Recall we assumed that no vertex rejected at step (i) and so 𝑢 has access to 𝑇 𝐺 .) • 𝑣 is the unique vertex in 𝑃 start that is at distance at most 𝑑 𝑣 from 𝐶 𝑣 . (again 𝑢 can check this because it has access to 𝑇 𝐺 .) • |𝑉 (𝑃 start )| + (LongestPaths[𝑣]) ⩾ 𝑚 This case corresponds to the case represented on Figure

  𝐶 𝑣 = 𝐶 𝑣 (0) The decomposition of an induced path in two consecutive paths 𝑃 start and 𝑃 end with the properties mentioned in the proof of Theorem 1.10.

		𝑃 end
	𝐶 𝑣 (2) 𝐶 𝑣 (1)	𝑣	𝑉 1
	𝐶 𝑣 (𝑑 𝑣 )		𝐶 𝑢 (2)
			𝐶 𝑢 (1)
			𝑢
	𝑉 ≼𝑢	𝑃 start
			𝐶 𝑢 = 𝐶 𝑢 (0)
	Fig. 5.

Claim 6.5

. There are at most two 𝐶 ∈ E 2 such that |𝐶 ∩ 𝑃 | ⩾ 2. And if there are exactly two, then 𝑃 does not contain any vertex from any other ECC 2 .

  0⩽𝑑 ⩽𝑘 -1 𝐶 𝑢 (𝑑) ⊆ 𝑉 ≼𝑢 . Thus, for every 𝑣 ∈ 0⩽𝑑 ⩽𝑘 -1 𝐶 𝑢 (𝑑) and every (𝐻, {ℎ}) ∈ P (𝐻 ), 𝑢 can check if HTable[𝑣, (𝐻 ′ , {ℎ})] is correct. If it is not correct, 𝑢 rejects. If no vertex rejects at this point, then HTable is correct. (iv) If 𝐺 ≼𝑢 has an induced 𝐻 , such that all the vertices in 𝐻 \ 𝑉 ≼𝑢 are in distinct ECC 2 's, then 𝑢 rejects (in particular, this is the case if 𝐻 ⊆ 𝑉 ≼𝑢 ). The last steps are similar to step (v) in the verification of Theorem 1.10: 𝑢 will check that it can not obtain a graph 𝐻 by extending a subgraph of 𝐺 ≼𝑢 into 𝐻 , using a subgraph 𝐻 ′ such that HTable[𝑣, (𝐻 ′ , {ℎ})] = 1 for some vertices 𝑣 and ℎ. (v) If 𝑢 ∈ 𝑉 2 , let 𝐶 𝑢 ∈ E 2 such that 𝑢 ∈ 𝐶 𝑢 . The vertex 𝑢 rejects if there exists two pointed graphs (𝐻 start , {ℎ}), (𝐻 end , {ℎ}) ∈ P (𝐻 ) which are complementary of each other in 𝐻 , and a vertex 𝑣 ∈ 𝐶 𝑣 (𝑑 𝑣 ) for some 𝐶 𝑣 ≠ 𝐶 𝑢 , 𝑑 𝑣 ⩽ 𝑘 -1, such that the following conditions are satisfied:

	𝐶 𝑣
			𝐶 𝑤
	𝑃 𝑣
		𝑃 𝑤
		𝑤
	𝐶 𝑣 (1) 𝐶 𝑣 (2)	𝑣	𝐶 𝑤 (1) 𝐶 𝑤 (2)
	𝐶 𝑣 (𝑑 𝑣 )	𝐶 𝑢 (2)	𝐶 𝑤 (𝑑 𝑤 )
		𝐶 𝑢 (1)
		𝑢
		𝑃 start
		𝐶 𝑢

  follows from Claim 6.10 that there are at most three distinct 𝐶 ∈ E 2 such that 𝑃 ∩ 𝐶 ≠ ∅. Claim 6.11. 𝑃 ∩ 𝑉 2 ≠ ∅ Proof. Recall 𝑉 1 ⊆ 𝑉 ≼𝑢 for every vertex 𝑢 ∈ 𝑉 . In step (iv) of the 𝑚-pathcheck, every vertex checks whether there is an induced path of length 𝑚 with vertex set in 𝑉 ≼𝑢 . ■ By applying Lemma 6.3 for 𝑚, we obtain that: Claim 6.12. There are at least two distinct 𝐶 ∈ E 2 such that |𝑃 ∩ 𝐶 | ⩾ 2. Claim 6.13. If there are exactly three 𝐶 ∈ E 2 such that 𝑃 ∩ 𝐶 ≠ ∅, at least one vertex rejects.

Any property can be certified with a quadratic number of bits in this model, with certificates encoding the adjacency matrix, see e.g.[START_REF] Feuilloley | Introduction to local certification[END_REF].

In the literature, these two cases are simply called subgraph and induced subgraph, but to better differentiate we often add non-induced or non-necessarily induced to qualify the first case.

For subgraph detection, induced subgraphs have been less popular, for no obvious reason, except maybe that they are difficult to manage. A paper that focuses on induced subgraphs is[START_REF] Nikabadi | Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters[END_REF].

The topic of broadcast versus unicast in local certification has been explored in[START_REF] Patt-Shamir | Proof-labeling schemes: Broadcast, unicast and in between[END_REF].

Remember that 𝑃 𝑘 denotes the path on 𝑘 vertices, and we will also use 𝐾 𝑘 for cliques on 𝑘 vertices.

To our knowledge, this observation has never been used in local certification, but can be considered as folklore.

Minimum spanning trees with polynomial weights have optimal certificate size Θ(log 2 𝑛)[START_REF] Korman | Proof labeling schemes[END_REF], but one of the log 𝑛's originates from the encoding of the weights, hence this is not very satisfactory.

We leave the precise unique identifier assignment implicit, for simplicity, but it is easy to create one, having the vertices of the first clique named 1 to 𝑛, then the second 𝑛 + 1 to 2𝑛 + 1, etc.

That is, we identify the vertices of each side of the bipartite graph with the vertices of each blob, e.g. in increasing order of identifiers.

This new definition allows us to compose different computations using certificates, which is not possible in general with the standard certification definition, because of its binary output.

Note that in theorem the verification radius is 2, but this result is just a component of a scheme with radius 𝑘 ⩾ 2, hence the ECC are still defined with respect to this general 𝑘.

ACKNOWLEDGMENTS

L. Feuilloley thanks the participants of the PODC-DISC zulip chat for references about high-low degree techniques. This work was supported by ANR project GrR (ANR-18-CE40-0032). L. Cook was supported by the Institute for Basic Science (IBS-R029-C1).

𝑣 𝐶 𝑣

𝐶 𝑣 (𝑑 𝑣 ) 𝐶 𝑢 𝑢 𝐻 start 𝐻 end Fig. 8. Illustration of the condition making 𝑢 reject at step (v) of the verification. Here, the graph 𝐻 is the one of Figure 6. The pointed graph (𝐻 end , {ℎ}) is the pointed graph (𝐻 ′ , {ℎ}) of Figure 6. .

• 𝐻 start is an induced subgraph of 𝐺 ≼𝑢 , included in 𝑉 ≼𝑢 , which contains at least one vertex from 𝐶 𝑢 • ℎ is mapped to 𝑣, and it is the only vertex in 𝐻 start ∩ ( 𝑑 ⩽𝑑 𝑣 𝐶 𝑣 (𝑑))

• HTable[𝑣, (𝐻 end , {ℎ})] = 1, where (𝐻 end , {ℎ}) is the complementary of (𝐻 start , {ℎ}) in 𝐻 An illustration is shown on Figure 8. (vi) If 𝑢 ∈ 𝑉 2 , let 𝐶 𝑢 ∈ E 2 such that 𝑐 ∈ 𝐶 𝑢 . The vertex 𝑢 rejects if there exists three pointed graphs (𝐻 start , {ℎ 1 , ℎ 2 }), (𝐻 (1) end , {ℎ 1 }), (𝐻 (2) end , {ℎ 2 }), and two vertices 𝑣 1 ∈ 𝐶 𝑣 1 (𝑑 𝑣 1 ), 𝑣 2 ∈ 𝐶 𝑣 2 (𝑑 𝑣 2 ) for some 𝑑 𝑣 1 , 𝑑 𝑣 2 ⩽ 𝑘 -1 where 𝐶 𝑣 1 , 𝐶 𝑣 2 are two different ECC 2 's different from 𝐶 𝑢 , such that the following conditions are satisfied:

• 𝐻 (1) end , 𝐻 (2) end are two disjoint induced subgraphs of 𝐻 • (𝐻 start , {ℎ 1 , ℎ 2 }) is the complementary in 𝐻 of the disjoint union of (𝐻 (1) end , {ℎ 1 }) and (𝐻 (2) end , {ℎ 2 }) • 𝐻 start is an induced subgraph of 𝐺 ≼𝑢 , included in 𝑉 ≼𝑢 , which contains at least vertex from 𝐶 𝑢 • ℎ 1 (resp. ℎ 2 ) is mapped to 𝑣 1 (resp. 𝑣 2 ), and it is the only vertex in 𝐻 start ∩ ( 𝑑 ⩽𝑑 𝑣 1 𝐶 𝑣 1 (𝑑)) (resp. in 𝐻 start ∩ ( 𝑑 ⩽𝑑 𝑣 2 𝐶 𝑣 2 (𝑑)))

• HTable[𝑣 1 , (𝐻 (1) end )] = 1 and HTable[𝑣 2 , (𝐻 (2) end )] = 1 An illustration is shown on Figure 9. (vii) If 𝑢 did not reject at this point, it accepts.

Correctness. Let us show that this certification scheme is correct. First, assume that 𝐺 contains an induced 𝐻 , ant let us show that for every assignment of certificates, at least one vertex rejects. If no vertex rejects at step (i) of the verification, then every vertex 𝑢 computed the ECC-table 𝑇 𝐺 and its witnessed graph 𝐺 ≼𝑢 (𝑢 knows also 𝑉 ≼𝑢 because it can be computed directly from 𝑇 𝐺 ). If no vertex rejects at step (iii), then HTable is also correct. Then, we have the following Claim 6.6, and its proof is analogous as proofs of Claims 6.5 and 6.3. Claim 6.6.

(1) There are at most three 𝐶 ∈ E 2 such that 𝐶 ∩ 𝐻 ≠ ∅. (2) If there is at most one 𝐶 ∈ E 2 such that |𝐶 ∩ 𝐻 | ⩾ 2, then there exists a vertex which rejects at step (iv) of the verification.

By Claim 6.6, we can assume that there are at least two 𝐶 ∈ E 2 such that |𝐶 ∩ 𝐻 | ⩾ 2. Now, there are two cases.

𝐶 𝑣 2 𝐻 (2) end Fig. 9. Illustration of the condition making 𝑢 reject at step (vi) of the verification. The graph 𝐻 is the one of Figure 6. The graph 𝐻 [START_REF] Bousquet | Local Certification of Graph Decompositions and Applications to Minor-Free Classes[END_REF] end is a path on two vertices and the graph 𝐻 [START_REF] Bousquet | Local certification of local properties: tight bounds, trade-offs and new parameters[END_REF] end is a triangle. ). Let 𝑢 ∈ 𝐶 3 . Then, we can decompose 𝐻 in three parts 𝐻 start , 𝐻 (1) end , 𝐻 (2) end satisfying the conditions making 𝑢 reject at step (vi).

Conversely, assume that 𝐺 does not have an induced 𝐻 , and let us show that there exists an assignment of the certificates such that every vertex accepts. This assignment is the following one: the prover attributes the certificates such that no vertex rejects in the local computation schemes of Theorems 4.4 and 4.5, and gives the correct value of HTable to every vertex. With such a certificate, a vertex can not reject at steps (i), (ii) and (iii). With exactly the same argument as in the proof of Theorem 1.11, a vertex can not reject at step (iv).

By contradiction, assume that a vertex 𝑢 rejects at step (v). Then, there exists two pointed graphs (𝐻 start , {ℎ}), (𝐻 end , {ℎ}) satisfying the conditions making 𝑢 reject at step (v). By the properties they satisfy, we can glue them in ℎ to obtain a graph 𝐻 , which is still induced in 𝐺, which is a contradiction. Similarly, if a vertex 𝑢 rejects at step (vi), there exists three pointed graphs (𝐻 start , {ℎ 1 , ℎ 2 }), (𝐻 (1) end , ℎ 1 ), (𝐻 (2) end , ℎ 2 ) satisfying the conditions making 𝑢 reject at step (vi). We can again glue them on ℎ 1 , ℎ 2 to obtain an induced 𝐻 in 𝐺, which is a contradiction. Thus, all the vertices accept at step (vii), which concludes the proof. □

We stated Theorem 1.11 with an induced subgraph perspective but one can easily remark that the proof technique is general enough to be directly extended to subgraphs rather than induced subgraphs. Indeed, we simply have to change the definition of HTable in such a way HTable[𝑣, (𝐻 ′ , {ℎ})] is equal to 1 if 𝐻 ′ is a subgraph of 𝑑 ⩽𝑑 𝑣 𝐶 𝑣 (𝑑) instead of an induced subgraph in order to get the same result. We actually think that our proof technique can be used more generally to get subquadratic bounds in the polynomial regime.

6.3 Upper bound for paths of length at most 3𝑘 -1 in Õ (𝑛) Theorem 1.12. For every 𝑘 ⩾ 2, we can certify 𝑃 3𝑘 -1 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 log 3 𝑛).

To prove this result, we will in fact prove the following Proposition 6.7, and Theorem 1.12 will be a simple corollary. While, until now, all the results where based on 𝜀 = 1 2 and the partition of the vertex set into two parts, we will use the whole power of our machinery in this proof by choosing an arbitrarily small value of 𝜀; this leads to new technicalities we have to deal with in the proof. Proposition 6.7. There exists 𝑐 > 0 such that, for all 0 < 𝜀 < 1, there exists a certification scheme for 𝑃 3𝑘 -1 -free graphs using at most 𝑐 𝜀 • log 2 𝑛 • 𝑛 1+𝜀 bits. Proof of Theorem 1.12 assuming Proposition 6.7. The certification in size 𝑂 (𝑛 log 3 𝑛) is the following one. Let 𝑛 be the number of vertices in the graph. The prover writes 𝑛 in the certificate of every vertex of the graph, and certifies the correctness of this information with 𝑂 (𝑛 log 𝑛) bits (by coding a spanning tree). Then, it uses the certification scheme given by Proposition 6.7, with 𝜀 = 1/log 𝑛. This uses 𝑂 (𝑛 log 3 𝑛) bits in total, since 𝑛 1/log 𝑛 is a constant. □

Proof of Proposition 6.7. Let 0 < 𝜀 < 1 and 𝑁 = 1 𝜀 . Let us describe a certification scheme for 𝑃 3𝑘 -1 -free graphs. We will show that it is correct and uses at most 𝑐 𝜀 • log 2 𝑛 • 𝑛 1+𝜀 bits, where 𝑐 is a constant independent of 𝜀. Let 𝐺 = (𝑉 , 𝐸) be a graph and 𝑛 = |𝑉 |.

Certification. Let us describe the certificates given by the prover to the vertices. First, the prover gives to every vertex its certificates in the local computation schemes of Theorems 4.4 and 4.5, so that each vertex 𝑢 can compute 𝑇 𝐺 and 𝐺 ≼𝑢 . These certificates have size 𝑂 ( 𝑛 1+𝜀 𝜀 log 2 𝑛). Then, as in the certification scheme of Theorem 1.10, the prover adds some information in the certificates, in another field, denoted by LongestPaths, which is identical in the certificates of all the vertices. In LongestPaths, the prover writes a table which has 𝑛 rows and 𝑁 columns. The rows are indexed with the identifiers of the vertices, and the columns by {1, . . . , 𝑁 }. Let 𝑣 ∈ 𝑉 and 𝑖 ∈ {1, . . . , 𝑁 }. If 𝑣 ∉ 𝐶 ∈ E 𝑖 0⩽𝑑 ⩽𝑘 -1 𝐶 (𝑑), we set LongestPaths[𝑣, 𝑖] := ⊥. Else, there exists a unique 𝐶 𝑣 ∈ E 𝑖 and 𝑑 𝑣 ⩽ 𝑘 -1 such that 𝑣 ∈ 𝐶 𝑣 (𝑑 𝑣 ). In this case, let 𝑃 𝑣 denote the longest induced path starting from 𝑣 and having all its other vertices in 0⩽𝑑 <𝑑 𝑣 𝐶 𝑣 (𝑑), and let us denote its length by ℓ (𝑃 𝑣 ). We set LongestPaths[𝑣, 𝑖] := ℓ (𝑃 𝑣 ).

Since LongestPaths has 𝑛 rows, 𝑁 columns, and each entry is written on at most log 𝑛 bits, its size it 𝑂 (𝑁 𝑛 log 𝑛). Thus, the overall size of each certificate remains 𝑂 ( 𝑛 1+𝜀 𝜀 log 2 𝑛). Verification. The verification of each vertex 𝑢 ∈ 𝑉 consists in the following steps:

(i) First, 𝑢 applies the verification of the local computation schemes given by Theorems 4.4 and 4.5.

If no vertex rejects, then every vertex 𝑢 computed its witnessed graph 𝐺 ≼𝑢 and the ECC-table 𝑇 𝐺 of 𝐺. (ii) Then, 𝑢 checks that the field LongestPaths is written the same in its certificate and the certificates of all its neighbors. If it is not the case, 𝑢 rejects. If no vertex rejects, LongestPaths is the same in the certificates of all the vertices in 𝐺. The next step will consist in checking its correctness.

Correctness. Let us show that this certification scheme is correct. First, assume that 𝐺 has an induced path 𝑃 of length 3𝑘 -1, and let us show that for every assignment of certificates, at least one vertex rejects. If no vertex rejects at step (i), then every vertex 𝑢 knows the ECC-table 𝑇 𝐺 , and its witnessed graph 𝐺 ≼𝑢 . If no vertex rejects in steps (ii) and (iii), then LongestPaths is correctly written in the certificates.

Let us decompose 𝑃 in three consecutive parts 𝑃 1 , 𝑃 2 , 𝑃 3 , having respectively 𝑘, 𝑘 -1, 𝑘 vertices. Let 𝑥 1 (resp. 𝑥 2 , 𝑥 3 ) be the vertex of maximum degree in 𝑃 1 (resp. in 𝑃 2 , 𝑃 3 ). Let 𝑖 1 , 𝑖 2 , 𝑖 3 ∈ {1, . . . , 𝑁 } be such that 𝑥 1 ∈ 𝑉 𝑖 1 , 𝑥 2 ∈ 𝑉 𝑖 2 and 𝑥 3 ∈ 𝑉 𝑖 3 (see Figure 10 for an illustration). Note that the distance between 𝑥 1 and 𝑥 2 is at most 2𝑘 -2. Similarly, the distance between 𝑥 2 and 𝑥 3 is at most 2𝑘 -2. The two following Claims 6.8 and 6.9 show that, in all cases, at least one vertex rejects. Claim 6.8. If 𝑖 2 ⩾ min(𝑖 1 , 𝑖 3 ), then at least one vertex reject at step (iv) of the verification.

Proof. Assume that 𝑖 2 ⩾ 𝑖 1 . Then, we have 𝑥 2 ∈ 𝐻 𝑖 1 . Since 𝑥 1 and 𝑥 2 are at distance at most 2𝑘 -2, there are in the same ECC 𝑖 1 . Thus, we have 𝑥 1 ≼ 𝑥 2 . Note also that, since 𝑥 1 is the vertex of maximum degree in 𝑃 1 , we have 𝑃 1 ⊆ 𝑉 ≼𝑥 1 . Thus, by transitivity, we have 𝑃 1 ⊆ 𝑉 ≼𝑥 2 . Moreover, we also have 𝑃 2 ⊆ 𝑉 ≼𝑥 2 . Finally, there are two cases: 11. The vertex 𝑢 1 (resp. 𝑢 3 ) is the only vertex in 𝑃 ∩ 𝐶 𝑥 1 (𝑑 1 ) (resp. in 𝑃 ∩ 𝐶 𝑥 3 (𝑑 3 )). The vertices 𝑢 1 and 𝑢 3 are at distance at most 2𝑘 -1 from each other. The vertex 𝑢 is such that its distance to 𝑢 1 is at most 𝑘, and its distance to 𝑢 3 is at most 𝑘 -1.

Proof. Without loss of generality, assume that 𝑖 2 ⩽ 𝑖 3 ⩽ 𝑖 1 . We have 𝑥 1 ∈ 𝐻 𝑖 3 . There are two cases, depending on whether 𝑥 1 and 𝑥 3 are in the same ECC 𝑖 3 or not.

• are at distance at most 𝑘. This is depicted on Figure 11. So 𝑃 ′ is an induced path in the view of 𝑢 at distance 𝑘. Let us denote its length by ℓ (𝑃 ′ ).

Since 𝑃 has length 3𝑘 -1, by definition of LongestPaths, we have:

Thus, the vertex 𝑢 rejects at step (vi). □ Conversely, assume that there is no induced 𝑃 3𝑘 -1 in 𝐺. Then, let us prove that with the certificates described above, no vertex rejects. It is straightforward that no vertex rejects at steps (i), (ii) and (iii). By contradiction, assume that a vertex 𝑢 rejects at step (iv). Then, there exists an induced path 𝑃 of length 3𝑘 -1 in 𝐺 ≼𝑢 which is included in 𝑉 ≼𝑢 . So 𝑃 is also induced in 𝐺, which is a contradiction. Finally, assume that a vertex 𝑢 rejects at step (v). Then, there is a path 𝑃 induced in the view of 𝑢 at distance 𝑘 and two vertices 𝑣 1 , 𝑣 2 satisfying the conditions making 𝑢 reject at step (v). Let 𝑖 ∈ {1, . . . , 𝑁 } be such that 𝑣 1 and 𝑣 2 are at distance at most 𝑘 -1 from two distinct ECC 𝑖 's, denoted by 𝐶 𝑣 1 and 𝐶 𝑣 2 . Let 𝑑 𝑣 1 (resp. 𝑑 𝑣 2 ) be such that 𝑣 1 ∈ 𝐶 𝑣 1 (𝑑 𝑣 1 ) (resp. 𝑣 2 ∈ 𝐶 𝑣 2 (𝑑 𝑣 2 )). By definition of LongestPaths, there exists a path 𝑃 𝑣 1 (resp. 𝑃 𝑣 2 ) which starts in 𝑣 1 (resp. 𝑣 2 ), which has all its other vertices in 0⩽𝑑 <𝑑 𝑣 1 𝐶 𝑣 1 (𝑑) (resp. in 0⩽𝑑 <𝑑 𝑣 2 𝐶 𝑣 2 (𝑑)), and such that ℓ (𝑃)+(ℓ (𝑃 𝑣 1 )-1)+(ℓ (𝑃 𝑣 2 )-1) ⩾ 3𝑘 -1. So we can glue the paths 𝑃 𝑣 1 , 𝑃 and 𝑃 𝑣 2 to obtain a path of length 3𝑘 -1 in 𝐺, which is still induced. This is a contradiction. Thus, all the vertices accept at step (vi). □ 6.4 Upper bound for paths of length 14 3 𝑘 -2 in Õ (𝑛 3/2 ) In this subsection we prove the following theorem. Theorem 1.13. For every 𝑘 ⩾ 2, we can certify 𝑃 ⌈ 14 3 𝑘⌉ -1 -free graphs by looking at distance 𝑘 with certificates of size 𝑂 (𝑛 3/2 log 2 𝑛).

Proof. Let 𝑚 = 14 3 𝑘 -1. Note that 𝑚 < 14 3 𝑘. Let us describe a certification scheme for 𝑃 𝑚 -free graphs, with certificates of size 𝑂 (𝑛 3/2 log 2 𝑛). Let 𝐺 = (𝑉 , 𝐸) be a graph and 𝑛 = |𝑉 |. Let 𝜀 = 1 2 . We will use the definitions of Section 4.2.1 with respect to 𝜀. We remind the reader of the following key pieces of notation.

• 𝑉 1 is the set of vertices with degree less than Certification. Let us describe the certificates given by the prover to the vertices. We give every vertex 𝑣 the certificates of Theorem 1.10 and some additional information denoted by LongestConstrainedPath. We repeat the definition of the certificates of Theorem 1.10 for the readers convenience: First, it gives to every vertex its certificates in the local computation schemes of Theorems 4.4 and 4.5, with 𝜀, so that each vertex 𝑢 can compute 𝑇 𝐺 and 𝐺 ≼𝑢 . This part of the certificate has size 𝑂 (𝑛 3/2 log 2 𝑛). Then the prover adds the field LongestPaths to each vertex. It has size 𝑂 (𝑛 log 𝑛).

For every 𝑣 ∈ 𝑉 , let us describe what information is stored in LongestConstrainedPath(𝑣). If 𝑣 ∈ 𝑉 2 or 𝑣 ∈ 𝑉 1 and 𝑣 has distance at least 𝑘 from every ECC 2 , then we set LongestConstrainedPath(𝑣) = ⊥. Otherwise, LongestConstrainedPath(𝑣) consists in a table having at most 𝑛 rows, and 4 columns. The rows are indexed by vertices of 𝐺. The content of each cell is the following. Let 𝑣 ′ ∈ 𝐶 𝑣 (𝑑 𝑣 ) \ {𝑣 }. Let 𝑄 denote the set 0⩽𝑑 <𝑑 𝑣 𝐶 𝑣 (𝑑). In other words, 𝑄 is the set of vertices in 𝐺 with that are strictly closer to 𝐶 𝑣 than 𝑣.

• In LongestConstrainedPath(𝑣) [𝑣 ′ , 1], the prover writes the length of the longest induced path starting from 𝑣 and having all the other vertices in 𝑄 ∪ {𝑣 ′ }. • In LongestConstrainedPath(𝑣) [𝑣 ′ , 2], the prover writes the length of the longest induced path starting from 𝑣 ′ and having all the other vertices in 𝑄 \ 𝑁 [𝑣]. • In LongestConstrainedPath(𝑣) [𝑣 ′ , 3], the prover writes the length of the longest induced path starting at 𝑣, ending in 𝑣 ′ , and having all the other vertices in 𝑄. • In LongestConstrainedPath(𝑣) [𝑣 ′ , 3], the prover writes the maximum sum of the lengths of two disjoint induced paths, which are anti-complete one to each other, which start respectively at 𝑣 and 𝑣 ′ , and which have all the other vertices in 𝑄.

Note that LongestPaths and LongestConstrainedPath both have size 𝑂 (𝑛 log 𝑛). Thus, the overall size of each certificate is 𝑂 (𝑛 3/2 log 2 𝑛).

Verification. The verification of each vertex 𝑢 ∈ 𝑉 consists in the following steps. First 𝑢 performs the 𝑚-pathcheck as described in Definition 6.2. (Recall 𝑚 = ⌈14𝑘/3⌉ -1.) We will refer to the steps of Definition 6.2 as step (i) -step (v).

Then 𝑢 performs the following additional steps: (vi) 𝑢 checks the correctness of LongestConstrainedPath(𝑢). Proof. Since 𝑃 passes through 𝐶 𝑢 and 𝐶 𝑣 , let us consider a connected subgraph of 𝑃, which is a path denoted by 𝑃 ′ , such that 𝑃 ′ starts in 𝐶 𝑢 and ends in 𝐶 𝑣 . Let 𝑢 be the last vertex in 𝑃 ′ ∩𝐶 𝑢 (𝑘 -1) before 𝑃 ′ passes through 𝐶 𝑣 . Since 𝑃 ′ goes from 𝑢 ∈ 𝐶 𝑢 (𝑘 -1) to 𝐶 𝑣 , then it contains at least 𝑘 other vertices after 𝑢 (at least one in 𝐶 𝑣 (𝑑) for each 𝑑 ∈ {0, . . . , 𝑘 -1}). Let us denote by 𝑋 the set of the 𝑘 vertices following 𝑢 in 𝑃 ′ . All the vertices in 𝑋 are at distance at most 𝑘 from 𝑢. By definition of 𝑢, we have 𝑋 ∩ 0⩽𝑑 ⩽𝑘 -1 𝐶 𝑢 (𝑑) = ∅. And since 𝛼 < 2 3 𝑘 and |𝑋 | = 𝑘, we have that 𝑋 ∩ 1⩽𝑑 ⩽𝑘 -1 𝐶 𝑣 (𝑑) ≠ ∅. We may assume that for each vertex 𝑥 1 ∈ 𝑋 ∩ B 𝑣 there are at least two other distinct vertices 𝑥 2 , 𝑥 3 ∈ 𝑉 (𝑃) ∩ B 𝑣 such that 𝑥 1 , 𝑥 2 , 𝑥 3 are all the same distance from 𝐶 𝑣 .

Let 𝐷 be the set of distances 𝑑 ∈ {1, 2, . . . , 𝑘 } for which some 𝑥 ∈ 𝑋 is at distance 𝑑 from 𝐶 𝑣 (i.e. 𝑥 ∈ 𝐶 𝑣 (𝑑)).

There are two cases:

𝑘 which also contradicts (3). In all cases, we get a contradiction. Thus, there exists 𝑑 𝑣 ∈ {1, . . . , 𝑘 -1} and a vertex 𝑣 ∈ 𝑋 ∩𝐶 𝑣 (𝑑 𝑣 ) such that |𝑃 ∩ 𝐶 𝑣 (𝑑 𝑣 )| = 2. ■ Using Claim 6.15, let us finish the proof by showing that 𝑢 rejects at step (viii).

Let 𝑢 ∈ 𝐶 𝑢 (𝑘 -1), 𝑑 𝑣 ∈ {1, . . . , 𝑘 -1} and 𝑣 ∈ 𝑃 ∩ 𝐶 𝑣 (𝑑 𝑣 ) at distance at most 𝑘 from 𝑢 such that |𝑃 ∩ 𝐶 𝑣 (𝑑 𝑣 )| = 2. Let 𝑣 ′ be the other vertex in 𝑃 ∩ 𝐶 𝑣 (𝑑 𝑣 ). Then, 𝑢 rejects at step (viii) of the verification. Indeed, there are several cases (see Figure 13 for an illustration):

• If 𝑃 has both endpoints in 𝑉 \ 𝑑 ⩽𝑑 𝑣 𝐶 𝑣 (𝑑) , the set of conditions (c) is satisfied.

• If 𝑃 has both endpoints in 𝑑 ⩽𝑑 𝑣 𝐶 𝑣 (𝑑), the set of conditions (d) is satisfied.

• If 𝑃 has exactly one endpoint in 𝑑 ⩽𝑑 𝑣 𝐶 𝑣 (𝑑), one of the sets of conditions (a) or (b) is satisfied. Indeed, Claim 6.15 proves more precisely that 𝑢 ∈ 𝑃 ∩ 𝐶 𝑢 (𝑘 -1), and that 𝑣 is among the 𝑘 next vertices after 𝑢 in 𝑃. Let 𝑤 be the vertex after 𝑣 in 𝑃 (which exists, otherwise 𝑣 is an endpoint of 𝑃 which would have both endpoints in 𝑑 ⩽𝑑 𝑣 𝐶 𝑣 (𝑑)). If 𝑤 ∈ 𝑑 ⩽𝑑 𝑣 𝐶 𝑣 (𝑑), then we are in case (a), else we are in case (b). Conversely, let us show that if 𝐺 is 𝑃 𝑚 -free, then no vertex rejects with the certificates described above. By definition, no vertex will reject in steps (i), (ii), (iii) and (vi). By contradiction, assume that there exists 𝑢 ∈ 𝑉 which (iv), (v), (vii) or (viii).

• If 𝑢 rejects at (iv), there exists an induced path 𝑃 of length 𝑚 in 𝐺 ≼𝑢 such that all the vertices in 𝑃 \ 𝑉 ≼𝑢 are in distinct ECC 2 's. So 𝑃 is also induced in 𝐺. • If 𝑢 rejects at step (v), with the same proof as in Theorem 1.10, we can reconstruct an induced path 𝑃 of length 𝑚 in 𝐺, which is a contradiction. • If 𝑢 rejects at step (vii), we can also reconstruct an induced path of length 𝑚 in 𝐺. Indeed, let 𝑃 𝑣 (resp. 𝑃 𝑤 ) be the path of length LongestPaths[𝑣] (resp. LongestPaths[𝑤]) which starts at 𝑣 (resp. 𝑤) and has all its other vertices in 𝑑 <𝑑 𝑣 𝐶 𝑣 (𝑑) (resp. in 𝑑 <𝑑 𝑤 𝐶 𝑤 (𝑑)). Then, we obtain an induced path of length 𝑚 by gluing 𝑃 𝑣 , 𝑃 start and 𝑃 𝑤 . • Finally, if 𝑢 rejects at step (viii), we can also construct an induced path 𝑃 of length 𝑚 in 𝐺, as depicted on Figure 13. In each case, the definition of LongestConstrainedPath[𝑣] ensures that the path obtained by gluing the parts is still induced in 𝐺. In all cases, we obtain an induced path 𝑃 of length 𝑚 in 𝐺, which is a contradiction. Thus, if 𝐺 is 𝑃 𝑚 -free, all vertices accept with the certificates described above. □