Detecting short directed cycles using rectangular matrix multiplication and dynamic programming

We present several new algorithms for detecting short fixed length cycles in digraphs. The new algorithms utilize fast rectangular matrix multiplication algorithms together with a dynamic programming approach similar to the one used in the solution of the classical chain matrix product problem. The new algorithms are instantiations of a generic algorithm that we present for finding a directed C k , i.e., a directed cycle of length k, in a digraph, for any fixed k 3. This algorithm partitions the prospective C k s in the input digraph G = (V, E) into O(log V ) classes, according to the degrees of their vertices. For each cycle class we determine, in O(E log V ) time, whether G contains a C k from that class, where c k = c k (#) is a constant that depends only on #, the exponent of square matrix multiplication. The search for cycles from a given class is guided by the solution of a small dynamic programming problem. The total running time of the obtained deterministic algorithm is therefore O(E k+1 V ).