Finding paths of length k in O∗(k2) time

We give a randomized algorithm that determines if a given graph has a simple path of length at least k in O(k2⋅poly(n)) time. Our method extends a recent O(23k/2⋅poly(n))⩽O(k2.83⋅poly(n)) algorithm of Koutis.