Número de descendentes de cada nó em um DAG

8

1) Existe um algoritmo melhor que o ingênuo O (| E |. | V |) para calcular o número de descendentes de cada vértice em um DAG?

2) Existe um algoritmo online para fazê-lo, assumindo que os nós sejam adicionados um por um e se conectem a um subconjunto não vazio dos nós existentes?

Contexto: Estou interessado no caso em que m = O (n), milhões de vértices, dezenas de milhões de arestas normalmente. Como alternativa, seria útil contar o número de descendentes que também são sumidouros.

Uma abordagem probabilística seria o hash min, como uma maneira de representar o conjunto de descendentes de cada nó. A união da estrutura min-hash é trivial e a cardinalidade da união pode ser estimada a partir do número de coincidências nos min-hashes.

No entanto, não tenho certeza de quão bem comportado isso seria ao propagar o DAG, intuitivamente, parece que os erros seriam compostos rapidamente.

Muito relacionado: /cstheory/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag E, na verdade, uma duplicata de: https: // cstheory.stackexchange.com/questions/18787/what-is-the-fastest-deterministic-algorithm-for-incremental-dag-reachability

graph-theory Arthur B
fonte
Você mudou sua pergunta. O (n ^ 2 + m) para o cenário 1 o ajudaria?
Niklas B.
Não seria rápido o suficiente, mas eu estaria interessado em ouvir como você faz isso.
Arthur B
O grau externo de seus nós é limitado? Ou geralmente, você tem alguma propriedade do gráfico que poderia ajudar a projetar um algoritmo mais rápido? Intuitivamente um DAG não é simples como um gráfico geral aqui, porque você pode decompor um gráficos gerais para SCCs que formam um DAG
Niklas B.
11
Minhas desculpas pela minha resposta anterior - isso foi definitivamente errado!
templatetypedef
2
Eu sugiro que você pergunte isso no CS.stackexchange.com. Minha intuição é que é um problema mais difícil do que parece. Se você generalizá-lo para o problema em que você tem pesos de nó e deseja saber para cada nó o peso total alcançável, é pelo menos tão difícil quanto o mesmo problema para gráficos gerais pela redução de SCC mencionada. Mas pode haver algumas técnicas para acelerar a computação para o tipo de gráficos que você está enfrentando
Niklas B.

Respostas:

4
  1. Classifique topologicamente os nós no seu DAG.
  2. Para cada nó N, defina N.QueryCount = 0.
  3. Para cada nó N, em ordem topológica reversa:
    • Set N.Descendants = {N} U {C.Descendants | C in N.Children}.
    • Rendimento (N, N.Descendants.Count)do algoritmo.
    • Se N.Parentsestiver vazio, você pode descartar N.Descendants.
    • Para cada Cno N.Children, incremento C.QueryCount. Se C.QueryCount == C.Parents.Count, você pode descartar C.Descendants.

É claro que isso é caro se os graus dos nós forem grandes. A complexidade do pior caso pode não ser significativamente melhor que o seu "algoritmo ingênuo" não especificado.

A questão é que esse é um problema muito difícil de resolver. Suponha que exista um DAG com milhões de nós, milhões de arestas, etc. Eu mostro a você esta parte do gráfico:

A--> B
 \-> C

Quantos descendentes Atem? O número de descendentes de Bmais o número de descendentes de Cmenos o número de descendentes comuns de Be C. É o terceiro termo que cria a dificuldade. Você não pode saber apenas o número de descendentes de Be C- também precisa saber quais são os descendentes.

Timothy Shields
fonte
11
Isso parece ser O (N * m), pelo menos,
Niklas B.
11
E o algoritmo ingênuo seria apenas fazendo acessibilidade (DFS ou BFS) a partir de cada nó
Niklas B.
@NiklasB. Se a união definida for O (1), então é O (n + m). Obviamente, a união de conjuntos não é, mas se os graus dos nós forem relativamente baixos, eles deverão ter um bom desempenho em termos de uso de CPU e RAM. EDIT: isso não está certo, por favor ignore.
amigos estão dizendo sobre timothy
11
Não tenho tanta certeza, mesmo que os graus sejam baixos, pode acontecer que muitos vértices tenham muitos sucessores. Para uma árvore binária desequilibrada (por exemplo, uma cadeia de nós) seria O (n ^ 2), a menos que você use união por peso (mas acho que isso não dá muito para o caso geral)
Niklas B .
@NiklasB. Ah, certo, porque os Descendantsconjuntos terão tamanho O (n) próximo ao final.
Timothy Shields
1

A listagem de todos os descendentes de todos os vértices pode produzir uma saída do tamanho O(n²), por exemplo, se o gráfico for um gráfico linear, o vértice sem aresta de entrada terá n - 1descendentes, o vértice a seguir n - 2e assim por diante.

Isso deixa a questão se você pode determinar o número de descendentes sem enumerá-los. Não posso provar, mas estou bastante confiante de que a resposta é não. Suponha um vértice xtem filhos ue v, em seguida, você tem que encontrar a cardinalidade da intersecção dos conjuntos de descendentes de ue vmas não há simplesmente nada que você conheça sobre esse conjunto - ue vnão podem compartilhar um único descendente ou eles podem ter o mesmo conjunto de descendentes .


fonte