Какие границы можно поставить для подсчета достижимых узлов в dag?

Дано это даг. Вы хотите пометить каждый узел тем, сколько узлов доступно из него. - тривиальная верхняя граница; является нижней границей (я думаю). Есть ли лучший алгоритм? Есть ли основания полагать, что нижняя граница может быть улучшена (связана: что именно известно о нижних границах для транзитивного замыкания)?Ω ( V + E $O(V(V+E))$$\Omega(V+E)$

Мотивация: я должен был сделать это пару раз, представляя следующие формулы как даг.

Изменить: Обратите внимание, что просто делая подсчитывает пути , а не достижимые узлы . (Я добавил это, потому что, по-видимому, многие думали, что это простое решение будет работать с помощью голосов, которые я видел в удаленном ответе.) Фактически, эта проблема возникает именно тогда, когда вы хотите сделать что-то интересное с «общими» частями, узлами, доступными для более одного пути. Кроме того, я говорю, дага, потому что, если они решаются, то решение орграфов легко.$c_x=1+\sum_{x\to y}c_y$

Транзитивное замыкание ориентированного графа с ребрами и вершинами может быть вычислено немного быстрее, чем время , но ненамного. алгоритм времени упоминается в примечании 2005 комки бумаги Чана на ССЦН (версия журнала в Algorithmica 2008). Небольшое улучшение можно найти в статье ICALP'08 «Новый комбинаторный подход к разреженным задачам графа», автор Blelloch, Vassilevska и Уильямс. При этом я не знаю, проще ли считать потомков, чем на самом деле их найтип О ( т п ) О ( п 2 + м н / войти п ) O ( п 2 + м н лог ( п 2 / м ) / войти 2 п $m$$n$$O(mn)$$O(n^2 + mn/\log n)$$O(n^2 + mn \log(n^2/m)/\log^2 n)$

$n^{\omega}$

Возможно, это не полезно в вашем контексте, но вы можете получить приближение с помощью Synopsis Diffusion (http://www.cs.cmu.edu/~sknath/sd.htm). Я думаю, что это делает O (V + E). Симуляция диффузии синопсиса на однопроцессоре выглядит для меня как O (V + E), (сначала нужно выполнить топологическую сортировку, которая также является O (V + E)).