Decreasing Verification Radius in Local Certification

Josef Erik Sedláček, Jan Matyáš Křišťan, Laurent Feuilloley, Jan Janoušek.

ALGOWIN 2024: 20th International Symposium on Algorithmics of Wireless Networks
doi:

This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verification of this certification needs to be done locally without the knowledge of the whole graph. More precisely, a distributed algorithm, called a verifier, is executed on each vertex. The verifier observes the local neighborhood up to a constant distance and either accepts or rejects. We examine the trade-off between the visibility radius and the size of certificates. We describe a procedure that decreases the radius by encoding the neighbourhood of each vertex into its certificate. We also provide a corresponding lower bound on the required certificate size increase, showing that such an approach is close to optimal.

This work was done mostly by Josef Erik Sedláček and Jan Matyáš Křišťan, two PhD students from CTU in Prague, who came to me with the idea. We discussed online several times, and here is the paper!