Testing Properties of Directed Graphs: Acyclicity and Connectivity

This paper initiates the study of testing properties of directed graphs. In particular, the paper considers the most basic property of directed graphs { acyclicity. Because the choice of representation aects the choice of algorithm, the two main representations of graphs are studied. For the adjacency-matrix representation, most appropriate for dense graphs, a testing algorithm is developed that requires query and time complexity of ), where is a distance parameter independent of the size of the graph. The algorithm, which can probe the adjacency matrix of the graph, accepts every graph that is acyclic, and rejects, with probability at least 2=3, every graph whose adjacency matrix should be modi ed in at least fraction of its entries so that it becomes acyclic. For the incidence list representation, most appropriate for sparse graphs, an jVj ) lower bound is proved on the number of queries and the time required for testing, where V is the set of vertices in the graph. Along wit