Como abordar problemas relacionados a gráficos dinâmicos

Eu fiz essa pergunta no stackoverflow genérico e fui direcionado aqui.

Será ótimo se alguém puder explicar como abordar problemas gráficos parciais ou totalmente dinâmicos em geral.

Por exemplo:

• Encontre o caminho mais curto entre dois vértices em um gráfico ponderado não direcionado para instâncias, quando uma aresta é removida em cada instância.$(u,v)$$n$
• Encontre o número de componentes conectados em um gráfico não direcionado para n instâncias quando uma aresta é removida em cada instância, etc.

Recentemente, encontrei esse gênero de problemas em um concurso de programação. Pesquisei na web e encontrei muitos trabalhos de pesquisa relacionados a gráficos dinâmicos [1,2]. Eu li alguns deles e não consegui encontrar nada direto (clustering, sparsification etc). Desculpe por ser vago.

Eu realmente aprecio se alguns podem fornecer indicadores para entender melhor esses conceitos.

1. Algoritmos de Gráfico Dinâmico por D. Eppstein, Z. Galil, GF Italiano (1999)
2. Caminhos mais curtos em gráficos dinâmicos de G. Nannicini, L. Liberti (2008)

É difícil fornecer técnicas concretas porque "dinâmico" pode significar uma grande variedade de coisas, e os algoritmos / resultados dependem do seu modelo. Abaixo está uma visão geral das preocupações. Aqui está um artigo que fornece uma visão geral de algumas preocupações e modelos diferentes (relacionados ao que Peter citou em outra resposta).

Para problemas dinâmicos em geral, os principais problemas são:

• você deseja uma solução exata em todos os casos ou a aproximação é permitida?
• você sabe alguma coisa sobre quais mudanças ocorrerão (por exemplo, uma distribuição de probabilidade) ou todas elas são igualmente prováveis?
• como o algoritmo aprende sobre as mudanças?

Um modelo dinâmico típico é algo como o seguinte:

1. Dado um gráfico, você deseja calcular alguma propriedade. Você tem permissão para calcular uma solução para o gráfico inicial.

2. Você recebe uma modificação: a borda é excluída. Calcule a propriedade no novo gráfico usando recursos limitados .$(e,f)$

3. Repita 2 por vezes.$n$

E aqui estão três modificações possíveis:

• Você não tem permissão para calcular a solução completa no início devido a limitações de informações / tempo / espaço (um exemplo é o algoritmo on - line )

• Na etapa 2, o algoritmo não é "informado" da modificação, mas precisa encontrar a modificação no gráfico consultando uma estrutura de dados ou algo assim.

• Um modelo distribuído (como Peter discute em outra resposta), onde as informações são descobertas localmente e o cálculo / alterações são feitos localmente.

Modelos dinâmicos geralmente são interessantes devido a limitações de recursos (por exemplo, tempo / espaço). Na etapa 2, se eu pudesse calcular uma resposta completa (como fiz na etapa 1), o problema será fácil, pois é apenas um problema repetido de gráfico estático . Estamos mais interessados ​​na menor quantidade de recursos necessária para calcular a alteração.

Modelos de gráficos dinâmicos foram estudados intensivamente em computação distribuída. Para algoritmos distribuídos, o cálculo é estruturado em rodadas e a topologia de gráficos (= rede) pode sofrer algumas alterações de rodada para rodada, que estão sob controle de um adversário. Além disso, todo nó do gráfico executa um algoritmo que pode enviar uma mensagem para seus vizinhos (atuais!). (Esta mensagem é a entrada do algoritmo dos vizinhos na próxima rodada.) O que torna as coisas interessantes é que um nó não "vê" o gráfico inteiro, mas apenas sua vizinhança local.

Os problemas considerados nessas configurações são, por exemplo, informações espalhadas onde cada nó no gráfico contém inicialmente um token e, eventualmente, você deseja que cada nó tenha visto cada token. O objetivo é projetar algoritmos que atinjam isso no menor número de rodadas, usando o menor número de mensagens. Veja [2] para uma pesquisa recente.

Para a configuração não distribuída, você pode olhar para [1], que é uma extensão do artigo que você mencionou.

[1] Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal, Fabio Vandin: Algoritmos sobre gráficos em evolução . ITCS 2012: 149-160

[2] Fabian Kuhn, Rotem Oshman: Redes dinâmicas: modelos e algoritmos . SIGACT News 42 (1): 82-96 (2011)

Com base nas respostas do @Peter (é um comentário muito longo, incluí como resposta esperando que alguém se beneficie).

Eu sugeriria a seguinte referência:

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: gráficos que variam no tempo e redes dinâmicas. IJPEDS 27 (5): 387-408 (2012)

$\Delta$

O que é realmente importante nessa classificação é que existem relações de inclusão entre as diferentes classes. Portanto, se você resolver um problema em uma determinada classe, você o resolverá em todas as outras classes em que estiver incluído.

Os mesmos autores apresentaram algoritmos de transmissão em alguns dos gráficos mencionados. Eles forneceram diferentes métricas de desempenho relacionadas ao tempo (ou seja, definição diferente do menor tempo). Na transmissão, a ideia é que cada nó construa uma visão da rede no domínio do tempo. Isso é feito ouvindo repetidamente os vizinhos e enviando informações aos vizinhos. Se estiver assumindo periodicidade, um nó poderá dizer qual é o caminho de tempo mais curto para outro nó. Ele usa essas informações no roteamento. Mais detalhes podem ser encontrados em:

Arnaud Casteigts, Paola Flocchini, Bernard Mans e Nicola Santoro: Computações determinísticas em gráficos que variam no tempo: Radiodifusão sob mobilidade não estruturada. IFIP TCS 2010: 111-124

$u$$v$$\{(u,x_1), (x_1, x _2), ...., (x _k, v)\}$$u$$v$$v$$u$

Eu assisti a uma palestra dos autores anteriores. Pelo meu entendimento, eles afirmam que estamos longe de ser capazes de lidar com algoritmos de gráficos dinâmicos (seguindo as definições que seguem). Que ainda estamos no caso de classes simples. De fato, eles afirmam que a maioria dos algoritmos de computação móvel apenas supõe que seus algoritmos sejam muito rápidos para serem executados enquanto a rede está em transição! (que eu acredito ter ouvido muito) - Ou simplesmente, assuma a periodicidade da aparência das bordas (consulte redes tolerantes a atrasos etc.)