Tester si un dag donné est un réseau

Question

On me donne un graphique acyclique dirigé (DAG) avec une source et un puits uniques. Existe-t-il un moyen efficace de tester si le ordre partiel représenté par ce graphique est un treillis?

En d'autres termes, je dois tester si deux sommets ont un unique la moins haute limite et la plus grande borne inférieure.

Depuis brève navigation, j'ai trouvé un algorithme $ o (n ^ 3) $ qui calcule explicitement la limite supérieure la moins élevée de chaque paire d'éléments. Y a-t-il un meilleur test?