More specifically, the dependence on n in this algorithm can be made linear, by the following method: compute a depth first search tree, and test whether this tree's depth is greater than 2d.
Конкретнее — зависимость от n в этом алгоритме можно сделать линейной следующим способом: строим дерево поиска в глубину и проверяем, больше глубина дерева величины 2d или нет.