Быстрый алгоритм подсчета количества ациклических путей на ориентированном графе

Короче говоря, мне нужен быстрый алгоритм для подсчета количества ациклических путей в простом ориентированном графе.

By simple граф Я имею в виду граф без петель или нескольких ребер. Путь может начинаться с любого узла и должен заканчиваться на узле, у которого нет исходящих ребер. Путь является ациклическим , если ни одно ребро не встречается в нем дважды.

Мои графы (эмпирические наборы данных) имеют только от 20 до 160 узлов, однако в некоторых из них много циклов, поэтому будет очень большое количество путей, и мой наивный подход просто недостаточно быстр для некоторых из имеющихся у меня графов.

В настоящее время я «спускаюсь» по всем возможным ребрам с использованием рекурсивной функции, отслеживая при этом какие узлы я уже посетил (и избегая их). Самое быстрое решение, которое у меня было до сих пор, было написано на C ++ и использует аргумент std :: bitset в рекурсивной функции для отслеживания того, какие узлы уже были посещены (посещенные узлы отмечены битом 1). Эта программа работает с образцом набора данных за 1-2 минуты (в зависимости от скорости компьютера). С другими наборами данных для запуска требуется больше суток или, по-видимому, намного больше.

Образец набора данных: http://pastie.org/1763781 (каждая строка представляет собой пару ребер)

Решение для образца набора данных (первое число - это узел, с которого я начинаю, второе число - это счетчик путей, начиная с этого узла, последнее число - это общее число путей): http://pastie.org/1763790

Пожалуйста, дайте мне знать, если у вас есть идеи об алгоритмах большей сложности. Меня также интересуют приблизительные решения (оценка количества путей с помощью некоторого подхода Монте-Карло). В конце концов, я также захочу измерить среднюю длину пути.

Edit: также опубликовано на MathOverflow под тем же заголовком, так как там это может быть более актуально. Надеюсь, это не противоречит правилам. Невозможно создать ссылку, так как на сайте не может быть более 2 ссылок ...