Dado um dag ponderado, existe um algoritmo O (V + E) para substituir cada peso pela soma de seus pesos ancestrais?

O problema, é claro, é a contagem dupla. É fácil o suficiente para certas classes de DAGs = uma árvore ou mesmo uma árvore serial-paralela. O único algoritmo que encontrei que funciona em DAGs gerais em tempo razoável é aproximado (difusão de sinopse), mas aumentar sua precisão é exponencial no número de bits (e eu preciso de muitos bits).

Histórico: esta tarefa é executada (várias vezes com pesos diferentes) como parte dos cálculos de probabilidade no BBChop (http://github.com/ealdwulf/bbchop), um programa para encontrar bugs intermitentes (por exemplo, uma versão bayesiana de ' git bisect '). O DAG em questão é, portanto, um histórico de revisões. Isso significa que é improvável que o número de arestas se aproxime do quadrado do número de nós; provavelmente será menor que k vezes o número de nós para algum k pequeno. Infelizmente, não encontrei outras propriedades úteis dos DAGs de revisão. Por exemplo, eu esperava que o maior componente triconnected crescesse apenas como raiz quadrada do número de nós, mas infelizmente (pelo menos na história do kernel do linux) cresce linearmente.

Assumimos que os pesos dos vértices podem ser números inteiros positivos arbitrários ou, mais precisamente, eles podem ser números inteiros positivos no máximo 2 ⁿ . Então a tarefa atual não pode ser executada mesmo em um limite de tempo ligeiramente mais fraco O ( n ² ), a menos que o fechamento transitivo de um gráfico direcionado arbitrário possa ser calculado em O ( n ² ), em que n indica o número de vértices. (Observe que um algoritmo de tempo O ( n ² ) para o fechamento transitivo será um avanço.) Esse é o contrapositivo da seguinte reivindicação:

Reivindicação . Se a tarefa atual puder ser executada no tempo O ( n ² ), o fechamento transitivo de um gráfico direcionado arbitrário dado como sua matriz de adjacência pode ser calculado no tempo O ( n ² ) (assumindo algum modelo computacional razoável).

Prova . Como pré-processamento, calculamos a decomposição de componentes fortemente conectados do gráfico direcionado G dado no tempo O ( n ² ) para obter um DAG G '. Observe que, se pudermos calcular o fechamento transitivo de G ′, podemos reconstruir o fechamento transitivo de G ' .

Agora atribua o peso 2 ⁱ a cada vértice i do DAG G 'e use o algoritmo para o problema atual. Então a representação binária da soma atribuída a cada vértice i descreve exatamente o conjunto de ancestrais de i , ou seja, calculamos o fechamento transitivo de G ′. QED .

O inverso da reivindicação também é válido: se você pode calcular o fechamento transitivo de um determinado DAG, é fácil calcular as somas necessárias com trabalho adicional no tempo O ( n ² ). Portanto, em teoria, você pode realizar a tarefa atual no tempo O ( n ^2.376 ) usando o algoritmo para o fechamento transitivo baseado no algoritmo de multiplicação da matriz Coppersmith-Winograd .

Edit : A revisão 2 e anterior não declararam explicitamente a suposição sobre o intervalo de pesos dos vértices. Per Vognsen apontou em um comentário que essa suposição implícita pode não ser razoável (obrigado!), E eu concordo. Mesmo que pesos arbitrários não sejam necessários em aplicativos, acho que essa resposta pode descartar algumas abordagens pela seguinte linha de raciocínio: “Se essa abordagem funcionasse, daria um algoritmo para os pesos arbitrários, que é descartado, a menos que seja transitivo. o fechamento pode ser calculado no tempo O ( n ² ). ”

Edit : A revisão 4 e anterior declararam a direção das arestas incorretamente.

Esta é uma expansão do meu comentário sobre a resposta de Tsuyoshi. Penso que a resposta negativa à pergunta pode ser incondicional.

Esse problema parece exigir operações de adição na pior das hipóteses, mesmo para gráficos com arestas . Portanto, não parece possível atingir o limite necessário.O ( n $\omega(n)$$O(n)$

Considere um gráfico consiste em vértices, organizados em uma grade. Os vértices em cada uma das linhas dependem precisamente de dois vértices na linha acima. A família é composta por gráficos como este, por combinações adequadas de valores de e , e arranjos adequados de arestas. r × c r r $G_{r,c}$$r \times c$$r$$r$$c$

Em particular, deixa e . Além disso, permita que os pesos dos vértices da linha superior sejam potências distintas de 2.c = 2 n / log $r = (\log\ n)/2$$c = 2n/\log\ n$

Cada um dos vértices na linha inferior dependerá dos vértices na linha superior. Até onde sei, existe um DAG específico com valores diferentes para cada um dos pesos da linha inferior, de modo que adições não reutilizáveis ​​são necessárias, em média, para cada uma dessas somas. ω(logn$\sqrt{n}$$\omega(\log\ n)$

No geral, isso gera um limite inferior para o número de adições, enquanto o número de arestas é .2 c ( r - 1 ) = O ( n $\omega(n)$$2c(r-1) = O(n)$

O ponto parece ser que a ordem parcial subjacente é densa, mas o DAG representa sua redução transitiva, que pode ser esparsa.

Isso está errado e é baseado em um mal-entendido sobre a questão. Agradeço a Tsuyoshi por apontar pacientemente o meu erro. Sair no caso de outros cometerem o mesmo erro.

$k$

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

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

Essa abordagem também deve funcionar bem se houver alguns nós com muitos predecessores imediatos, desde que sejam relativamente pouco frequentes.