Quais limites podem ser colocados na contagem de nós alcançáveis ​​em um dag?

23

Dado é um dag. Você deseja rotular cada nó por quantos nós são acessíveis a partir dele. é um limite superior trivial; é um limite inferior (eu acho). Existe um algoritmo melhor? Há razões para acreditar que o limite inferior pode ser melhorado (relacionado: o que exatamente se sabe sobre limites inferiores para fechamento transitivo)?O(V(V+E))Ω(V+E)

Motivação: tive que fazer isso algumas vezes enquanto representava as fórmulas folclóricas como adagas.

Edit: Observe que simplesmente fazer conta caminhos , nós não alcançáveis . (Adicionei isso porque, aparentemente, muitas pessoas pensavam que essa solução simples funcionaria com os votos que eu vi em uma resposta agora excluída.) De fato, esse problema aparece precisamente quando você deseja fazer algo interessante com partes 'compartilhadas', nós alcançáveis ​​por mais de um caminho. Além disso, digo dag, porque se eles forem resolvidos, então é fácil resolver dígrafos.cx=1+xycy

Radu GRIGore
fonte
Este parece ser um caso especial (definindo todos os pesos para um) de cstheory.stackexchange.com/questions/736/…
Suresh Venkat
@ Suresh: Se pesos arbitrários dificultam o problema me parece outra pergunta interessante.
Radu GRIGore

Respostas:

10

O fechamento transitivo de um gráfico direcionado com arestas e n vértices pode ser calculado um pouco mais rápido que o tempo de O ( m n ) , mas não muito. Um algoritmo de tempo O ( n 2 + m n / log n ) é mencionado em uma nota de rodapé do artigo WADS de 2005 de Chan sobre APSP (versão do periódico Algorithmica 2008). Uma ligeira melhora em O ( n 2 + m n log ( n 2 / m ) / log 2 nmnO(mn)O(n2+mn/registron) pode ser encontrada no documento da ICALP'08 "Uma nova abordagem combinatória para problemas de gráficos esparsos", de Blelloch, Vassilevska e Williams. Dito isto, não sei se contar descendentes é mais fácil do que encontrá-losO(n2+mnregistro(n2/m)/registro2n)

virgi
fonte
4
Além disso, veja o artigo de Edith Cohen "Estrutura de estimativa de tamanho com aplicações para fechamento e acessibilidade transitiva". Ele fornece um algoritmo aleatório que estima o número de descendentes com eficiência.
virgi 9/09/10
Observe que esses resultados se aplicam a todos os gráficos direcionados, não apenas aos DAGs.
tonfa
Sim. O resultado também se aplica à versão ponderada mencionada em cstheory.stackexchange.com/questions/736/…
virgi
7

Eu acho que você pode usar a multiplicação de matrizes para calcular o fechamento transitivo do DAG e, em seguida, usar o número de vizinhos externos conforme a contagem desejada. Não sou especialista em literatura, mas acho que você pode calcular o fechamento transitivo ao mesmo tempo que a multiplicação de matrizes, ou seja, tempo: http://www.computer.org/portal/web/csdl/doi/10.1109/ ACSSC.1995.540810 .nω

Bart Jansen
fonte
Obrigado, isso é interessante! Devo acrescentar que os dags que representam fórmulas simbólicas tendem a ser esparsos, por isso estou um pouco mais interessado nesse caso.
Radu GRIGore 26/08/10
1

Talvez não seja útil no seu contexto, mas você pode obter uma aproximação usando o Synopsis Diffusion (http://www.cs.cmu.edu/~sknath/sd.htm). Eu acho que torna O (V + E). A simulação da difusão de sinopse em um uniprocessador parece-me O (V + E), (você precisa primeiro fazer uma classificação topológica, que também é O (V + E)).

Ealdwulf
fonte