Riconoscere se il digrafo dato in input contiene o meno un ciclo e' chiaramente un punto chiave del problema. Stiamo parlando del riconoscere se un dato digrafo e' o meno un DAG, celebre problema la cui buona caratterizzazione viene dalla possibilita' di ordinare su una linea tutti i nodi di modo che gli archi guardino tutti in avanti (ogni ordine parziale e' estendibile ad un ordine totale) tutte le volte che non siano presenti cicli.