Existe um algoritmo para manter eficientemente as informações de conexão de um DAG na presença de inserções / exclusões?

17

Dado um gráfico acíclico direcionado, , é possível oferecer suporte eficiente às seguintes operações?G(V,E)

  • L um bisConnected(G,a,b) : determina se existe um caminho em do nó para o nóGab
  • a b Glink(G,a,b) : Adiciona uma aresta de a no gráficoabG
  • a b Gunlink(G,a,b) : remove a aresta de para emabG
  • add(G,a) : adiciona um vértice a G
  • remove(G,a) : remove um vértice de G

Algumas notas:

  • Se não permitirmos , parece que seria fácil manter as informações de conexão, usando uma estrutura de dados do tipo conjunto separado.unlink
  • Obviamente, o pode ser implementado usando a pesquisa de profundidade ou largura, usando a representação ingênua do gráfico com base em ponteiro. Mas isso é ineficiente.isConnected

Espero um tempo constante ou logarítmico amortizado para as três operações. Isso é possível?

Justin Kilpatrick
fonte
3
Relacionado: A versão do gráfico não direcionado já foi solicitada antes. Existe um algoritmo online para acompanhar os componentes em um gráfico não direcionado em mudança?
Tsuyoshi Ito
11
Você poderia explicar como resolver o caso mais simples (sem desvincular) usando uma estrutura de dados do tipo conjunto separado?
jbapple
@ Tsuyoshi - os links dessa pergunta parecem interessantes, eu estou dando uma olhada neles agora.
precisa
(1) Você está procurando um algoritmo de gráfico dinâmico para acessibilidade direcionada com a restrição de que o gráfico é um DAG. Se não me engano, a acessibilidade dinâmica direcionada é muito mais difícil que a contraparte não direcionada, mas aqui a propriedade DAG pode ajudar. (2) removeTambém remove as bordas do incidente? Nesse caso, exigir que a operação seja de tempo O (log n) pode ser demais para se esperar….
Tsuyoshi Ito

Respostas:

19

O problema que você descreveu é a acessibilidade totalmente dinâmica do DAG (também conhecido como fechamento transitivo totalmente dinâmico nos DAGs). É chamado de totalmente dinâmico, pois as pessoas também estudam as versões nas quais somente exclusões são possíveis (então é chamada de acessibilidade decremental) e onde apenas inserções são possíveis (chamadas de acessibilidade incremental).

Existem algumas vantagens e desvantagens entre o tempo de atualização e o tempo de consulta. Seja o número de arestas en o número de vértices. Para os DAGs, Demetrescu e Italiano (FOCS'00) forneceram uma estrutura de dados aleatória que suporta atualizações (inserções ou exclusões de arestas) no tempo O ( n 1,58 ) e consultas de acessibilidade no tempo O ( n 0,58 ) (inserções / exclusões de nós também são suportadas , em O (1) tempo); esse resultado foi estendido por Sankowski (FOCS'04) para trabalhar com gráficos direcionados gerais. Também para DAGs, Roditty (SODA'03) mostrou que é possível manter a matriz de fechamento transitivo no tempo total O ( m n + I · n 2 + D ), ondemnn1.58n0.58mn+I·n2+D é o número de inserções, D o número de exclusões e, claro, o tempo de consulta é O ( 1 ).ID1

Para gráficos direcionados gerais, são conhecidos os seguintes tempos (atualização, consulta): (O ( ), O (1)) (Demetrescu e Italiano FOCS'00 (amortizado), Sankowski FOCS'04 (pior caso)) ( O ( m n2 ),O(mn )) (Roditty, Zwick FOCS'02), (O (m+nlogn), O (n)) (Roditty, Zwick STOC'04), (O (n 1,58 ), O (n 0,58 )) e (O (n 1.495 ), O (n 1.495 )) de Sankowski (FOCS'04).O(nm+nlognnn1.58n0.58n1.495n1.495

Obter um tempo de consulta polilogarítmica, sem aumentar muito o tempo de atualização, é um grande problema em aberto, mesmo para DAGs.

virgi
fonte
11
Obrigado pela sua resposta. Embora eu tenha que dizer que estou decepcionado com o quão pobres esses limites são. :(
Justin Kilpatrick
11
Uma pergunta relacionada: você poderia me indicar referências sobre problemas mais simples, acessibilidade incremental e acessibilidade decremental para DAGs?
23411 Justin Kilpatrick
Isso não parece muito melhor do que a abordagem ingênua dfs (O(1),O(n^2))ou (O(m),O(n+m)).
Thomas Ahle
4

Acho que os melhores resultados até agora são discutidos em "Manutenção de matrizes dinâmicas para fechamento transitivo totalmente dinâmico" . Esse artigo discute um algoritmo aleatório com tempo de consulta e tempo de atualização O ( n 1,58 ) .O(n0.58)O(n1.58)

(Isso cobre apenas a primeira versão da sua pergunta, com linke unlinkmas sem adde remove.)

jbapple
fonte
Os limites são construídos no algoritmo de Strassen, então a constante é enorme.
Thomas Ahle