On the Time Required to Detect Cycles and Connectivity in Directed Graphs

Abstract

It is shown that when a directed graph is represented as a binary connection matrix, the problem of finding the shortest path between two nodes of a directed graph, and the problem of determining whether the directed graph has a cycle require at least $O(n^{2})$ operations. Thus the presently known best algorithms are optimal to within a multiplicative constant.