Relating Two Property Testing Models for Bounded Degree Directed Graphs

by Artur Czumaj, Pan Peng and Christian Sohler

Oded's comments

When studying testing properties of directed graphs, in a model analogous to the bounded-degree model of undirected graphs, one should make two (orthogonal) distinctions. The first distinction is between properties of the directed graph, which are sensitive to the orientation of edges, and properties of the underlying undirected graph (i.e., the undirected graph obtained from the directed graph when ignoring the orientation of edges). The second distinction is between a model in which the tester can make queries regarding both out-going and in-coming edges and a model in which one can only make queries about outgoing edges.

This work studies the gap between these two models, showing that if a property can be tested with a constant number of queries in the bi-directional query model, then it can be tested in a sublinear number of queries in the uni-directional query model. The transformation does not preserve one-sided error probability, and this is inherent, since there are properties that have a constant-query one-sided error tester in the first model but no sublinear-query one-sided error tester in the second model.

(Indeed, I have already mentioned this work in my report of The Sublinear Algorithms Workshop (JHU, Jan. 2016).)

The original abstract

See the program webpage of STOC'16.


Back to list of Oded's choices.