Componentes incrementais fortemente conectados

Para um gráfico direcionado em mudança, eu gostaria de manter informações sobre componentes fortemente conectados. As operações gráficas são incrementais: somente adição de vértice e adição de aresta. Quais estruturas de dados atingem a complexidade amortizada mais conhecida para essas operações?

Se o gráfico não fosse direcionado, a resposta seria a estrutura de localização de união. E como os gráficos não direcionados podem ser vistos como casos especiais de gráficos direcionados, o limite inferior (ainda que ligeiramente) superconstante é transferido.

Para um limite superior linear, os componentes fortemente conectados podem ser calculados do zero após cada adição de borda, sem reciclar nenhum dado. Gostaria de saber se existe alguma maneira de fazer melhor.

No cenário em que preciso disso, de alguma forma, espero que os SCCs não triviais sejam a exceção e não a regra. E na ausência de ciclos, posso atingir o tempo linear no total (que é o tempo constante amortizado por operação). [EDIT:] Deixe-me esclarecer o que quero dizer. É claro que, na ausência de ciclos, não preciso acompanhar os CECs. O tempo constante amortizado é para o que faço na minha configuração, além de me preocupar com os SCCs.

Portanto, eu também estaria interessado em estruturas de dados que, em geral, não são melhores que o limite superior acima, mas usam tempo constante amortizado por operação, desde que o gráfico permaneça um DAG.

Que eu saiba, o melhor algoritmo para componentes decrementais fortemente conectados é apresentado em [1] com total de atualização esperado.$O(m \sqrt{n} \log n)$

[1] Acessibilidade decrescente de fonte única e componentes fortemente conectados em Õ (m√n) Tempo total de atualização - Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, Nikos Parotsidis - https://ieeexplore.ieee.org / document / 7782945 - FOCS 2016

Atualização: O novo melhor algoritmo para SCCs decrementais é apresentado em [5]$O(m (\log n)^4)$

[5] Componentes decrescentemente fortemente conectados e acessibilidade de fonte única em tempo quase linear - Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen - https://arxiv.org/abs/1901.03615 - aceito no STOC 2019

O melhor algoritmo para componentes incrementais fortemente conectados é apresentado em [2] com tempo de atualização por borda.$O(m^{1/2})$

[2] Detecção de ciclo incremental, ordenação topológica e manutenção de componentes fortes - Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen e Robert Endre Tarjan - https://arxiv.org/abs/1105.2397 - 2012 ACM Trans. Algoritmos

É uma questão em aberto se esses dois problemas podem ser resolvidos mais rapidamente.

Para componentes fortemente dinâmicos totalmente conectados , limites inferiores condicionais são conhecidos. Os limites inferiores de pior caso também são conhecidos pela manutenção decrescente / incremental de componentes fortemente conectados. Para detalhes, consulte [3] e [4].

[3] Unificação e fortalecimento da dureza para problemas dinâmicos por meio da conjectura de multiplicação de vetores matriciais on-line - Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak - https://arxiv.org/pdf/1511.06773.pdf - STOC 2015

[4] Conjecturas populares implicam limites inferiores fortes para problemas dinâmicos - Amir Abboud, Virginia Vassilevska Williams - https://arxiv.org/pdf/1402.0054.pdf - FOCS 2014

Todos esses resultados são válidos para gráficos gerais. Melhores resultados são conhecidos para gráficos planares.

O resultado que você menciona sobre os DAGs é bem conhecido:

Eficiência amortizada de uma estrutura de dados de recuperação de caminho - GF Italiano - https://www.sciencedirect.com/science/article/pii/0304397586900988 - TCS 1986