Dado un dag ponderado, ¿existe un algoritmo O (V + E) para reemplazar cada peso con la suma de sus pesos ancestrales?

El problema, por supuesto, es contar dos veces. Es bastante fácil de hacer para ciertas clases de DAG = un árbol, o incluso un árbol serie-paralelo. El único algoritmo que he encontrado que funciona en DAG generales en un tiempo razonable es aproximado (difusión de sinopsis), pero aumentar su precisión es exponencial en el número de bits (y necesito muchos bits).

Antecedentes: esta tarea se realiza (varias veces con diferentes 'pesos') como parte de los cálculos de probabilidad en BBChop (http://github.com/ealdwulf/bbchop), un programa para encontrar errores intermitentes (es decir, una versión bayesiana de ' git bisect '). El DAG en cuestión es, por lo tanto, un historial de revisión. Eso significa que es poco probable que el número de aristas se acerque al cuadrado del número de nodos, es probable que sea menor que k veces el número de nodos para algunos k pequeños. Lamentablemente, no he encontrado ninguna otra propiedad útil de los DAG de revisión. Por ejemplo, esperaba que el componente triconectado más grande creciera solo como la raíz cuadrada del número de nodos, pero lamentablemente (al menos en la historia del kernel de Linux) crece linealmente.

Suponemos que los pesos de vértice pueden ser enteros positivos arbitrarios, o más precisamente, pueden ser enteros positivos como máximo 2 ⁿ . Entonces, la tarea actual no se puede realizar incluso en un límite de tiempo ligeramente más débil O ( n ² ), a menos que el cierre transitivo de un gráfico dirigido arbitrario se pueda calcular en tiempo O ( n ² ), donde n denota el número de vértices. (Tenga en cuenta que un algoritmo de tiempo O ( n ² ) para el cierre transitivo será un gran avance). Este es el contrapositivo de la siguiente afirmación:

Reclamo . Si la tarea actual se puede realizar en el tiempo O ( n ² ), el cierre transitivo de un gráfico dirigido arbitrario dado como su matriz de adyacencia se puede calcular en el tiempo O ( n ² ) (suponiendo algún modelo computacional razonable).

Prueba . Como preprocesamiento, calculamos la descomposición de componentes fuertemente conectados del gráfico dirigido G dado en el tiempo O ( n ² ) para obtener un DAG G '. Tenga en cuenta que si podemos calcular el cierre transitivo de G ', podemos reconstruir el cierre transitivo de G' .

Ahora asigne el peso 2 ⁱ a cada vértice i del DAG G 'y use el algoritmo para el problema actual. Luego, la representación binaria de la suma asignada a cada vértice i describe exactamente el conjunto de antepasados ​​de i , en otras palabras, hemos calculado el cierre transitivo de G '. QED .

Lo contrario de la afirmación también es válida: si puede calcular el cierre transitivo de un DAG dado, es fácil calcular las sumas requeridas por trabajo adicional en el tiempo O ( n ² ). Por lo tanto, en teoría, puede lograr la tarea actual en el tiempo O ( n ^2.376 ) utilizando el algoritmo para el cierre transitivo basado en el algoritmo de multiplicación de matriz de Coppersmith-Winograd .

Editar : la Revisión 2 y anteriores no establecían la suposición acerca del rango de pesos de vértices explícitamente. Per Vognsen señaló en un comentario que esta suposición implícita puede no ser razonable (¡gracias!), Y estoy de acuerdo. Incluso si no se necesitan pesos arbitrarios en las aplicaciones, supongo que esta respuesta podría descartar algunos enfoques mediante la siguiente línea de razonamiento: “Si este enfoque funcionara, daría un algoritmo para los pesos arbitrarios, que se descarta a menos que sea transitivo el cierre se puede calcular en el tiempo O ( n ² ) ".

Editar : la revisión 4 y anteriores indicaron incorrectamente la dirección de los bordes.

Esta es una expansión de mi comentario sobre la respuesta de Tsuyoshi. Creo que la respuesta negativa a la pregunta puede hacerse incondicional.

Este problema parece requerir operaciones de suma en el peor de los casos, incluso para gráficos con bordes O ( n ) . Por lo tanto, no parece posible alcanzar el límite requerido.$\omega(n)$$O(n)$

Considere un gráfico consiste en vértices r × c , dispuestos en una cuadrícula. Los vértices en cada una de las filas r dependen precisamente de dos vértices en la fila de arriba. La familia consta de gráficos como este, para combinaciones adecuadas de valores de r y c , y disposiciones adecuadas de bordes.$G_{r,c}$$r \times c$$r$$r$$c$

En particular, dejar que y c = 2 n / log n . Además, deje que los pesos de los vértices de la fila superior sean potencias distintas de 2.$r = (\log\ n)/2$$c = 2n/\log\ n$

Cada uno de los vértices en la fila inferior dependerá de vértices en la fila superior. Por lo que yo puedo decir, hay entonces existe un DAG específica con diferentes valores para cada uno de los pesos de fila inferior, de manera queω(logn)se requieren adiciones no reutilizables en promedio para cada una de estas sumas.$\sqrt{n}$$\omega(\log\ n)$

$\omega(n)$$2c(r-1) = O(n)$

El punto parece ser que el orden parcial subyacente es denso, pero el DAG representa su reducción transitiva, que puede ser escasa.

Esto está mal y se basa en un malentendido sobre la pregunta. Gracias a Tsuyoshi por señalar pacientemente mi error. Dejar en caso de que otros cometan el mismo error.

$k$

$k$$O(k|V|)$

$O(|V|+|E|)$

Este enfoque también debería funcionar bien si hay algunos nodos con muchos predecesores inmediatos, siempre que sean relativamente poco frecuentes.