¿Qué límites se pueden poner en el conteo de nodos alcanzables en un dag?

Dado es un dag. Desea etiquetar cada nodo por la cantidad de nodos a los que se puede acceder desde él. es un límite superior trivial; Ω ( V + E ) es un límite inferior (creo). ¿Hay un mejor algoritmo? ¿Hay alguna razón para creer que el límite inferior se puede mejorar (relacionado: qué se sabe exactamente sobre los límites inferiores para el cierre transitivo)$O(V(V+E))$$\Omega(V+E)$

Motivación: tuve que hacer esto un par de veces mientras representaba las siguientes fórmulas como dags.

Editar: Tenga en cuenta que simplemente haciendo cuenta las rutas , no los nodos accesibles . (Agregué esto porque aparentemente muchas personas pensaron que esta solución simple funcionaría por los votos que vi en una respuesta ahora eliminada). De hecho, este problema aparece precisamente cuando quieres hacer algo interesante con partes 'compartidas', nodos accesibles por Más de un camino. Además, digo dag, porque si se resuelven, entonces resolver dígrafos es fácil.$c_x=1+\sum_{x\to y}c_y$

El cierre transitivo de un gráfico dirigido con aristas y n vértices se puede calcular un poco más rápido que el tiempo O ( m n ) , pero no mucho. Un algoritmo de tiempo O ( n 2 + m n / log n ) se menciona en una nota al pie del documento WADS 2005 de Chan sobre APSP (versión de revista en Algorithmica 2008). Una ligera mejora a O ( n 2 + m n log ( n 2 / m ) / log 2$m$$n$$O(mn)$$O(n^2 + mn/\log n)$ se puede encontrar en el documento ICALP'08 "Un nuevo enfoque combinatorio para problemas de gráficos dispersos" de Blelloch, Vassilevska y Williams. Dicho esto, no sé si contar descendientes es más fácil que encontrarlos$O(n^2 + mn \log(n^2/m)/\log^2 n)$

Creo que puede usar la multiplicación de matrices para calcular el cierre transitivo del DAG, y luego usar el número de vecinos externos como los conteos deseados. No soy un experto en literatura, pero creo que puede calcular el cierre transitivo al mismo tiempo que la multiplicación de matrices, es decir, tiempo: http://www.computer.org/portal/web/csdl/doi/10.1109/ ACSSC.1995.540810 .$n^{\omega}$

Tal vez no sea útil en su contexto, pero puede obtener una aproximación usando Synopsis Diffusion (http://www.cs.cmu.edu/~sknath/sd.htm). Creo que eso lo hace O (V + E). Simular la difusión de la sinopsis en un uniprocesador me parece O (V + E), (primero debe hacer una clasificación topológica, que también es O (V + E)).