Testing the (s, t)-disconnectivity of graphs and digraphs
Property testing is concerned with constant-time algorithms for deciding whether a given object satisfies a predetermined property or is far from satisfying it. In this paper, we consider testing properties related to the connectivity of two vertices in sparse graphs. We present one-sided error testers for (s, t)-disconnectivity with query complexity 2(O(1/epsilon)) for digraphs and O(1/epsilon(2)) for graphs, where is an error parameter. Furthermore, we show that these algorithms are the best possible in view of query complexity, i.e., we give matching lower bounds for two-sided error testers for both cases. We also give a constant-time algorithm for testing the (s, t)-disconnectivity of a directed bounded-degree hypergraph, which can be used to test the satisflability of Horn SAT. (C) 2012 Elsevier B.V. All rights reserved.
property testing horn sat disconnectivity general graph model bounded-degree model