2025/02/02 by Dan Alden Baterisna, Baterisna, Dan Alden, Yi‐Jun Chang +1
Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2502.00676
openalex publication_date 2025/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 labels. Examples of such properties include planarity, Hamiltonicity, k-colorability, H-minor-freeness, admitting a perfect matching, and having a vertex cover of a given size. Our proof labeling schemes improve upon a recent result by Fraigniaud, Montealegre, Rapaport, and Todinca (Algorithmica 2024), which achieved the same result for graphs of bounded treewidth but required O(log2 n)-bit labels. Our improved label size O(log n) is optimal, as it is well-known that any proof labeling scheme that accepts paths and rejects cycles requires labels of size Ω(log n). Our result implies that graphs with pathwidth at most k can be certified using O(log n)-bit labels for any fixed constant k. Applying the Excluding Forest Theorem of Robertson and Seymour, we deduce that the class of F-minor-free graphs can be certified with O(log n)-bit labels for any fixed forest F, thereby providing an affirmative answer to an open question posed by Bousquet, Feuilloley, and Pierron (Journal of Parallel and Distributed Computing 2024).