Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph-Freeness

Abstract

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 $\ensuremath{\mathcal{O}}(n^{1-\epsilon/(3+\alpha)})$ 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 $\ensuremath{\mathcal{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 $\ensuremath{\mathcal{O}}(\sqrt{n})$ instead of, what would be expected, Ω(n ^2/3).