Optimal local certification on graphs of bounded pathwidth

Dan Alden Baterisna, Yi-Jun Chang

We present proof labeling schemes for graphs with bounded pathwidth that can decide any graph property expressible in monadic second-order (MSO) logic using $O(\log n)$-bit vertex…