Brief announcement: Local certification of graph decompositions and applications to minor-free classes

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron

DISC 2021: 35th International Symposium on Distributed Computing, October 4-8, 2021, Freiburg, Germany



Full version at OPODIS
Open access publisher's version Arxiv full version Prerecorded DISC video


Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph $G$ to a given graph class $G$. Such certifications with labels of size $O(log n)$ (where $n$ is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors.

In this paper, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor $H$, $H$-minor-free graphs can indeed be certified with labels of size $O(log n)$. We also show matching lower bounds with a new simple proof technique.


See the page of the OPODIS full version.