Abstract
A prooflabeling scheme (PLS) for a boolean predicate Π on labeled graphs is a mechanism used for certifying the legality with respect to Π of global network states in a distributed manner. In a PLS, a certificate is assigned to each processing node of the network, and the nodes are in charge of checking that the collection of certificates forms a global proof that the system is in a correct state, by exchanging the certificates once, between neighbors only. The main measure of complexity is the size of the certificates. Many PLSs have been designed for certifying specific predicates, including cyclefreeness, minimumweight spanning tree, planarity, etc.
In 2021, a breakthrough has been obtained, as a "metatheorem" stating that a large set of properties have compact PLSs in a large class of networks. Namely, for every MSO₂ property Π on labeled graphs, there exists a PLS for Π with O(log n)bit certificates for all graphs of bounded treedepth. This result has been extended to the larger class of graphs with bounded treewidth, using certificates on O(log² n) bits.
We extend this result even further, to the larger class of graphs with bounded cliquewidth, which, as opposed to the other two aforementioned classes, includes dense graphs. We show that, for every MSO₁ property Π on labeled graphs, there exists a PLS for Π with O(log² n)bit certificates for all graphs of bounded cliquewidth. As a consequence, certifying families of graphs such as distancehereditary graphs and (induced) P₄free graphs (a.k.a., cographs) can be done using a PLS with O(log² n)bit certificates, merely because each of these two classes can be specified in MSO₁. In fact, we show that certifying P₄free graphs can be done with certificates on O(log n) bits only. This is in contrast to the class of C₄free graphs (which does not have bounded cliquewidth) which requires Ω̃(√n)bit certificates.
BibTeX  Entry
@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2023.20,
author = {Fraigniaud, Pierre and Mazoit, Fr\'{e}d\'{e}ric and Montealegre, Pedro and Rapaport, Ivan and Todinca, Ioan},
title = {{Distributed Certification for Classes of Dense Graphs}},
booktitle = {37th International Symposium on Distributed Computing (DISC 2023)},
pages = {20:120:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959773010},
ISSN = {18688969},
year = {2023},
volume = {281},
editor = {Oshman, Rotem},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19146},
URN = {urn:nbn:de:0030drops191467},
doi = {10.4230/LIPIcs.DISC.2023.20},
annote = {Keywords: CONGEST, Proof Labelling Schemes, cliquewidth, MSO}
}
Keywords: 

CONGEST, Proof Labelling Schemes, cliquewidth, MSO 
Collection: 

37th International Symposium on Distributed Computing (DISC 2023) 
Issue Date: 

2023 
Date of publication: 

05.10.2023 