Límites más bajos en el tiempo de ejecución de los algoritmos gráficos

8

¿Existen límites inferiores no triviales en el tiempo de ejecución de los algoritmos gráficos en RAM / PRAM / modelos de computación? No estoy buscando los resultados de NP-Hardness aquí.

El siguiente es un resultado que pude encontrar [ver ref L92]:

  • 3-Colorear un ciclo n requiere tiempo .Ω(Iniciar sesión∗⁡norte)

Tenía curiosidad por saber si ha habido algún progreso / trabajo en la dirección de obtener límites más bajos para problemas como: rutas más cortas (con / sin pesos negativos), Mincut, st Flujos máximos, coincidencia máxima (cardinalidad / ponderado). Cualquier referencia relacionada con esto es muy apreciada y útil.

Referencia

[ L92 ] N. Linial, Localidad en algoritmos de gráficos distribuidos, SIAM Journal on Computing, 1992, 21 (1), pp. 193-201

EDITAR: Según lo sugerido por Robin Kothari en los comentarios, estoy haciendo la pregunta más dirigida.

cc.complexity-theory reference-request graph-algorithms lower-bounds rizwanhudda
fuente
55
Sin restringir el modelo, una respuesta adecuada a esta pregunta podría continuar por páginas. Además de la restricción a los problemas de gráficos, esta pregunta básicamente es "¿Qué límites inferiores se conocen en CS?" Y la restricción a los problemas de gráficos no es fuerte, ya que en los modelos en los que podemos probar buenos límites inferiores para algún problema (por ejemplo, transmisión, árboles de decisión, complejidad de comunicación), también podemos probar buenos límites inferiores para problemas de gráficos.
Robin Kothari
@RobinKothari He editado la pregunta ahora, estoy buscando límites inferiores en los modelos PRAM / RAM. ¿Sugieres más cambios?
rizwanhudda

Respuestas:

3

En el modelo PRAM sin operaciones de bit , se conocen límites inferiores bastante fuertes. Por ejemplo, en este modelo, no se puede resolver min-corte en de tiempo en procesadores [1].O(norte)2O(norte)

A pesar de ser un modelo restringido, es lo suficientemente fuerte como para calcular el determinante de manera eficiente, e incluye la mayoría de los algoritmos estándar para problemas de optimización combinatoria de polivinilos. Vea aquí , aquí o el documento original para más detalles.

[1] Mulmuley, K. Límites inferiores en un modelo paralelo sin operaciones de bits . SIAM J. Comput., 28 (4), 1460–1509, 1999. ( desde la página web del autor sin paywall )

Joshua Grochow
fuente