Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun.

*STACS 2024:
41st International Symposium on Theoretical Aspects of Computer Science
*

doi: 10.4230/LIPICS.STACS.2024.21

Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun.

*STACS 2024:
41st International Symposium on Theoretical Aspects of Computer Science
*

doi: 10.4230/LIPICS.STACS.2024.21

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.
For many classic global properties, like checking the acyclicity of
the network, the optimal size of the certificates depends on the
size of the network, $n$.
In this paper, we focus on properties for which the size of the
certificates does not depend on $n$ but on other parameters.
We focus on three such important properties and prove tight bounds
for all of them. Namely, we prove that the optimal certification
size is: $\Theta(\log k)$ for $k$-colorability (and even exactly
$\lceil \log k \rceil$ bits in the anonymous model while previous
works had only proved a $2$-bit lower bound); $(1/2)\log t+o(\log t)$
for dominating sets at distance $t$ (an unexpected and
tighter-than-usual bound) ; and $\Theta(\log \Delta)$ for perfect
matching in graphs of maximum degree $\Delta$ (the first non-trivial
bound parameterized by $\Delta$).
We also prove some surprising upper bounds, for example, certifying
the existence of a perfect matching in a planar graph can be done
with only two bits. In addition, we explore various specific cases
for these properties, in particular improving our understanding of
the trade-off between locality of the verification and certificate size.

Sébastien presented the paper at
JGA 2023.