Limites inferiores no tempo de execução dos algoritmos de gráfico

8

Existe algum limite inferior não trivial no tempo de execução dos algoritmos de gráfico na RAM / PRAM / modelos de computação? Não estou procurando os resultados da dureza NP aqui.

A seguir está um resultado que eu pude encontrar [veja ref L92]:

  • 3-A coloração de um ciclo n requer tempo .Ω(log∗⁡n)

Fiquei curioso para saber se houve algum progresso / trabalho no sentido de obter limites mais baixos para problemas como: Caminhos mais curtos (com / sem pesos negativos), Mincut, st Fluxos máximos, Correspondência máxima (cardinalidade / ponderada). Quaisquer referências relacionadas a isso são muito apreciadas e úteis.

Referência

[ L92 ] N. Linial, localidade em algoritmos de gráfico distribuído, SIAM Journal on Computing, 1992, 21 (1), pp. 193-201

EDIT: Como sugerido por Robin Kothari nos comentários, estou tornando a pergunta mais direcionada.

cc.complexity-theory reference-request graph-algorithms lower-bounds rizwanhudda
fonte
5
Sem restringir o modelo, uma resposta adequada a essa pergunta poderia continuar nas páginas. Além da restrição de problemas gráficos, esta pergunta é basicamente perguntando "Quais limites inferiores são conhecidos no CS?" E a restrição para problemas gráficos não é forte, já que em modelos nos quais podemos provar bons limites inferiores para algum problema (por exemplo, streaming, árvores de decisão, complexidade da comunicação), também podemos provar bons limites inferiores para problemas gráficos.
27612 Robin Kothari
@RobinKothari Eu editei a pergunta agora, estou procurando limites mais baixos nos modelos PRAM / RAM. Você sugere mais alterações?
rizwanhudda

Respostas:

3

No modelo PRAM sem operações de bit , são conhecidos limites inferiores bastante fortes. Por exemplo, neste modelo, não é possível resolver min-cut no tempo em processadores [1].O(n)2O(n)

Apesar de ser um modelo restrito, é forte o suficiente para computar o determinante com eficiência e inclui a maioria dos algoritmos padrão para problemas de otimização combinatória em politempo. Veja aqui , aqui ou o documento original para mais detalhes.

[1] Mulmuley, K. Limites inferiores em um modelo paralelo sem operações de bit . SIAM J. Comput., 28 (4), 1460–1509, 1999. ( da página do autor sem paywall )

Joshua Grochow
fonte