





















We revisit the relation between two fundamental property testing models for bounded-degree directed graphs: the bidirectional model in which the algorithms are allowed to query both the outgoing edges and incoming edges of a vertex, and the unidirectional model in which only queries to the outgoing edges are allowed. Czumaj, Peng and Sohler [STOC 2016] showed that for directed graphs with both maximum indegree and maximum outdegree upper bounded by $d$, any property that can be tested with query complexity $O_{\varepsilon,d}(1)$ in the bidirectional model can be tested with $n^{1-Ω_{\varepsilon,d}(1)}$ queries in the unidirectional model. In particular, if the proximity parameter $\varepsilon$ approaches $0$, then the query complexity of the transformed tester in the unidirectional model approaches $n$. It was left open if this transformation can be further improved or there exists any property that exhibits such an extreme separation. We prove that testing subgraph-freeness in which the subgraph contains $k$ source components, requires $Ω(n^{1-\frac{1}{k}})$ queries in the unidirectional model. This directly gives the first explicit properties that exhibit an $O_{\varepsilon,d}(1)$ vs $Ω(n^{1-f(\varepsilon,d)})$ separation of the query complexities between the bidirectional model and unidirectional model, where $f(\varepsilon,d)$ is a function that approaches $0$ as $\varepsilon$ approaches $0$. Furthermore, our lower bound also resolves a conjecture by Hellweg and Sohler [ESA 2012] on the query complexity of testing $k$-star-freeness.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。