Compact local certification of MSO properties for several tree-like parameters
Time: 14:00 -- Location: LRI, 445
summary: Local certification is interested in assigning labels (called certificates) to the vertices of a graph,
in order to certify a certain property about said graph, or the correctness of a data-structure distributed on
the graph. For the verification to be local, a vertex may only "see" its neighbourhood. A classical measure of
performance in a local certification is the size of its certificates.
In this work, we are interested in studying the compact certification of certain graphs properties, with respect
to some tree-like graph properties. Precisely, we are interested in obtaining metatheorems for local certification,
regarding some tree-like properties. We outline a proof for the compact local certification in graphs of bounded treewidth.
This result, obtained by Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport and Ioan Todinca, states that for every boolean
predicate on graphs definable in the monadic second-order (MSO) logic on graphs, there exists a local certification
requiring O(log² n)-bits certificate in graphs of bounded treewidth.