An Optimal Separation Between Two Property Testing Models for Bounded Degree Directed Graphs

Abstract

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_{ε,d}(1) in the bidirectional model can be tested with n^{1-Ω_{ε,d}(1)} queries in the unidirectional model. In particular, {if the proximity parameter ε 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-1/k}) queries in the unidirectional model. This directly gives the first explicit properties that exhibit an O_{ε,d}(1) vs Ω(n^{1-f(ε,d)}) separation of the query complexities between the bidirectional model and unidirectional model, where f(ε,d) is a function that approaches 0 as ε 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.