← 研踪 PaperTrailarXiv:2604.04466 · v2
A characterization of one-sided error testable graph properties in bounded degeneracy graphs
首次提交 2026-04-06 14:32
版本更新 2026-11-02 15:39
雷达观测 2026-11-04 23:42
摘要
We consider graph property testing in $p$-degenerate graphs under the random neighbor oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by sampling uniform neighbors of vertices, and a property is testable with one-sided error if its query complexity is independent of the graph size. It is known that one-sided error testable properties for minor-closed families are exactly those that can be defined by forbidden subgraphs of bounded size. However, the much broader class of $p$-degenerate graphs allows for high-degree ``hubs" that can structurally hide forbidden subgraphs from local exploration. In this work, we provide a complete structural characterization of all properties testable with one-sided error in $p$-degenerate graphs. We show that testability is determined by how copies of the forbidden graphs can share their high-degree vertices: $\mathcal{F}$-freeness is testable if and only if, for every member $H$, every set of roles of $H$ that may be played by high-degree vertices, and every pattern of dependencies between these roles, some member of $\mathcal F$ can be assembled from pieces of copies of $H$ glued according to this pattern. Our results define the exact structural boundary for testability under these constraints, accounting for both the connectivity of individual forbidden subgraphs and the collective behavior of the properties they define.
作者备注：To appear in SODA 2027
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-02 15:39 · 最新观测版本
A characterization of one-sided error testable graph properties in bounded degeneracy graphs
We consider graph property testing in $p$-degenerate graphs under the random neighbor oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by sampling uniform neighbors of vertices, and a property is testable with one-sided error if its query complexity is independent of the graph size. It is known that one-sided error testable properties for minor-closed families are exactly those that can be defined by forbidden subgraphs of bounded size. However, the much broader class of $p$-degenerate graphs allows for high-degree ``hubs" that can structurally hide forbidden subgraphs from local exploration. In this work, we provide a complete structural characterization of all properties testable with one-sided error in $p$-degenerate graphs. We show that testability is determined by how copies of the forbidden graphs can share their high-degree vertices: $\mathcal{F}$-freeness is testable if and only if, for every member $H$, every set of roles of $H$ that may be played by high-degree vertices, and every pattern of dependencies between these roles, some member of $\mathcal F$ can be assembled from pieces of copies of $H$ glued according to this pattern. Our results define the exact structural boundary for testability under these constraints, accounting for both the connectivity of individual forbidden subgraphs and the collective behavior of the properties they define.
查看此版本解读 →查看此版本原文 ↗