# Quick read: Testability and local certification

05 Oct 2022Hi! To start this new academic year, I’m experimenting a different format.
I skimmed through a paper I was curious about, and this post is a very
short summary of the context and results.
The paper is: *Testability and local certification of monotone properties
in minor-closed classes* (arxiv page,
ICALP version),
by Louis Esperet and
Sergey Norin.

## Property testing

The paper is about property testing and local certification of graph properties. I’ll start with a few definitions for the testing part.

In the following, for concreteness, one can think of planarity as the property we look at. A graph $G$ is $\epsilon$-far from a property $P$ if one needs to modify at least $\epsilon |E(G)|$ adjacencies (= replacing edges by non-edges or vice-versa) to get a graph having property $P$. In property testing we are interested in the question of how much we need to know about the graph to be able to decide whether it satisfies property $P$ or is $\epsilon$-far from it. Since we are not going to know the entire graph, it is usually impossible to have exact answers, which is why we don’t try to answer correctly for graphs that are very close to having the property (which are likely to be false positive).

There are various ways to query the graph to gain information about it, but
in this paper the model is the *random neighbor oracle*.
In this model, a
query can either ask to reveal a random vertex, or a random
neighbor of a vertex that has already been revealed. This is similar to
what is called the *sparse model*.

We are interested in the question: what can be tested with a constant number of such queries? In the other words, for which property $P$ can we design an algorithm (the tester) that makes a constant number of random neighbor oracle queries and decides whether the graph has property $P$ or is $\epsilon$-far from it. Note that by “constant” we mean that the number of queries does not grow with the size of the graph, but it does depend on $\epsilon$.

Such an algorithm will necessarily make mistakes and only randomized
algorithms make sense.
Here the answer will always be correct when the graph satisfies $P$, thus the
tester is said to have *one-sided error*.

## $\mathcal{H}$-free, monotone, minor-closed

Before stating the results of the paper, we need a bit of graph theory
vocabulary.
A class of graphs is
*minor-closed*
if it is stable by edge and vertex
removals, and by
edge contractions.
Robertson-Seymour theorem
states that this is equivalent to say that the class is defined
by a finite set of forbidden minors, that is, a finite set of graphs that
cannot be obtained by edge and vertex removals, and by edge contractions.
(You can check that planar graphs are minor-closed, and the corresponding
list of forbidden minors is {$K_5,K_{3,3}$}.)

A class of graphs is *monotone* if it is closed by taking subgraphs, that
is, closed by edge and vertex removals.
The equivalent of Robertson-Seymour theorem here would be “this is
equivalent to having a finite set of forbidden subgraphs”, but this is wrong.
Consider the bipartite graphs. They are closed by subgraphs, but to define
bipartite graphs via forbidden subgraphs one needs an *infinite* family of
subgraphs: all the cycles of odd length.
Therefore there is another notion: for a finite family $\mathcal{H}$ of
graphs, the $\mathcal{H}$-free graphs are the ones that do not have a graph
of $\mathcal{H}$ as a subgraph.

Note that being $\mathcal{H}$-free for some $\mathcal{H}$ implies that the class is monotone, but not the reverse.

## Theorem

The main theorem of the paper is the following.

**Theorem:** For every minor-closed class $\mathcal{G}$, and any monotone
property $P$, one can test with one-sided error whether a graph in $\mathcal{G}$
has property $P$.

Remember that we are in the setting with a constant number of random neighbor queries, and note that we restrict the input: instead of any graph, we promise that the input comes from a given minor-closed class. (A minor technicality here: the class of all graph is minor-closed, but the theorem actually holds only for proper minor-closed classes, i.e. the ones that are not the set of all graphs.)

This results improves on a previous result by Czumaj and Sohler that holds only for properties that are $\mathcal{H}$-free. I think this theorem is pretty amazing, because of its generality. Even having results about say bipartiteness is interesting, and here the only hypothesis are just sort of stability conditions (monotonicity and minor-closure).

## Approximate local certification

The techniques used to prove the theorem above can also be used to prove results about local certification. Defining local certification is a bit too long for this post so I will assume that the reader knows the concept. Otherwise, a reference is this introduction to the topic I wrote recently.

Actually, the result is about *approximate local certification*: if the graph
has the property, then there is a certificate assignment that convinces all
the nodes, and if the graph is $\epsilon$-far from the property, no
certificate assignment can convince all the nodes. Note that nothing is
randomized here.

To state the result we need one more graph definition: a graph class is
*summable* if for any pair of graphs $G_1$, $G_2$ in the class, the
disjoint union of $G_1$ and $G_2$ is also in the class.

**Theorem:** For any minor-closed class $\mathcal{G}$, and any monotone
summable property $P$, it is possible to approximately certify the property
$P$ for the graphs of $\mathcal{G}$, with constant-size certificates (and
constant-size view).

This improves on a result by Elek that requires bounded degree, and it is actually generalized in the paper to graphs of bounded asymptotic dimension instead of minor-closed graphs. (I hope to blog about asymptotic dimension soon.) Also, if one removes the summability assumption, then the same results holds but with logarithmic size certificates. This is interesting to me because it gives some approximate answer to the question of whether minor-closed classes have compact certification.