Optimal local certification on graphs of bounded pathwidth
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913674150543360 |
|---|---|
| author | Baterisna, Dan Alden Chang, Yi-Jun |
| author_facet | Baterisna, Dan Alden Chang, Yi-Jun |
| contents | 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(\log^2 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_00676 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal local certification on graphs of bounded pathwidth Baterisna, Dan Alden Chang, Yi-Jun Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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(\log^2 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). |
| title | Optimal local certification on graphs of bounded pathwidth |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.00676 |