Es gibt einen probabilistischen Algorithmus, der prüft, ob ein Graph in der Zeit einen einfachen Pfad der Länge von mindestens hat. Darüber hinaus gibt der Algorithmus immer „NEIN“ aus, wenn der Graph keinen solchen Pfad hat.