Relating two property testing models for bounded degree directed graphs

We study property testing algorithms in directed graphs (digraphs) with maximum indegree and maximum outdegree upper bounded by d . For directed graphs with bounded degree, there are two different models in property testing introduced by Bender and Ron (2002). In the bidirectional model , one can access both incoming and outgoing edges while in the unidirectional model one can only access outgoing edges. In our paper we provide a new relation between the two models: we prove that if a property can be tested with constant query complexity in the bidirectional model, then it can be tested with sublinear query complexity in the unidirectional model. A corollary of this result is that in the unidirectional model (the model allowing only queries to the outgoing neighbors), every property in hyperfinite digraphs is testable with sublinear query complexity.

Authors

• Artur Czumaj
• Pan Peng 0001
• Christian Sohler

Keywords

• directed graph algorithms
• graph property testing
• sampling based algorithms