Optimal Local Certification on Graphs of Bounded Pathwidth

We present proof labeling schemes for graphs with bounded path-width that can decide any graph property expressible in monadic second-order (MSO2) 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.

Authors

Institutions

Publication Details

Published
2025-06-13
DOI
https://doi.org/10.1145/3732772.3733503
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Optimal Local Certification on Graphs of Bounded Pathwidth

Yi‐Jun Chang, Dan Alden Baterisna
Advanced Graph Theory Research
article

Optimal Local Certification on Graphs of Bounded Pathwidth

Yi‐Jun Chang, Dan Alden Baterisna
article en

Abstract

We present proof labeling schemes for graphs with bounded path-width that can decide any graph property expressible in monadic second-order (MSO2) 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.

National University of Singapore (SG)
Ministry of Education - Singapore
Openalex Percentile: Top 85%
Advanced Graph Theory Research
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Optimal Local Certification on Graphs of Bounded Pathwidth — Yi‐Jun Chang, Dan Alden Baterisna · (2025) | TGRS Research Map | TGRS