We study property testing in directed graphs in the bounded degree model, where we assume that an algorithm may only query the outgoing edges of a vertex, a model proposed by Bender and Ron [4]. As our first main result, we we present the first property testing algorithm for strong connectivity in this model, having a query complexity of O(n~(1-∈/(3+α)) for arbitrary α > 0; it is based on a reduction to estimating the vertex indegree distribution. For subgraph-freeness we give a property testing algorithm with a query complexity of O(n~(1-1/k)), where k is the number of connected componentes in the queried subgraph which have no incoming edge. We furthermore take a look at the problem of testing whether a weakly connected graph contains vertices with a degree of least 3, which can be viewed as testing for freeness of all orientations of 3-stars; as our second main result, we show that this property can be tested with a query complexity of O(n~(1/2)) instead of, what would be expected, Ω(n~(2/3)).
展开▼
