מירב זהבי

Given a digraph G, two vertices s,t∈V(G) and a non-negative integer k, the LONG DIRECTED (s,t)-PATH problem asks whether G has a path of length at least k from s to t. We present a simple algorithm that solves LONG DIRECTED (s,t)-PATH in time O^⋆(4.884^k). This results also in an improvement upon the previous fastest algorithm for LONG DIRECTED CYCLE.