¿Reduce el uso de espacio de conectividad st con múltiples pases?

20

Suponga que un gráfico con vértices se presenta como un flujo de bordes, pero se permiten múltiples pases sobre el flujo.n mGnm

Monika Rauch Henzinger, Prabhakar Raghavan y Sridar Rajagopalan observaron que el espacio es necesario para determinar si hay un camino entre dos vértices dados en , si se permiten pases sobre los datos. (Consulte también la versión del informe técnico ). Sin embargo, no proporcionan un algoritmo para lograr este límite. Supongo que un algoritmo óptimo realmente ocuparía espacio en un modelo informático realista, ya que uno tiene que distinguir los vértices diferentes si no puede indexar la memoria utilizando punteros de tamaño constante.G k O ( ( nΩ(n/k)GknO((nlogn)/k)n

¿Cómo se puede decidir la conectividad gráfica con pasa usando el espacio ?O ( ( nkO((nlogn)/k)

Si solo se permite una pasada, los datos de entrada se pueden almacenar como una partición del conjunto de vértices, fusionando conjuntos si se ve un borde entre vértices en dos conjuntos diferentes. Esto claramente requiere como máximo espacio. Mi pregunta es sobre : ¿cómo se pueden usar más pases para reducir el espacio requerido?k > 1O(nlogn)k>1

(Para evitar la trivialidad, es un parámetro que no puede estar limitado a priori por una constante, y los límites de espacio son expresiones que involucran funciones de y ).n kknk


Actualización: incluso para sería realmente útil tener una forma de almacenar solo vértices. ¿O hay realmente un límite inferior más fuerte para alguna constante , independientemente de ?n / 2 c n c kk=2n/2cnck

András Salamon
fuente
¿Cómo independientemente de ? Si puede ser muy grande, entonces la conectividad st se puede resolver en el espacio O ( log 2 n ) , por lo que existe la posibilidad de un algoritmo, pero como lo muestra el azotlichid, probablemente no en O ( n log n / k ) . kO(log2n)O(nlogn/k)
domotorp
Tenga en cuenta que la eliminación de pasadas de Guha y McGregor para algoritmos aleatorios funciona en la dirección opuesta, utilizando más espacio para permitir menos pasadas (aunque el espacio adicional es grande si el error deseado es pequeño). Esta pregunta pregunta si al usar más pases, uno puede reducir el uso de espacio.
András Salamon

Respuestas:

8

Es un problema abierto de larga data encontrar un algoritmo para la conectividad st que se ejecute simultáneamente en un espacio sub-lineal y en un tiempo polinómico, una tarea más fácil a la que apunta. Dichos algoritmos son conocidos para la versión no dirigida , pero incluso estos requieren un gran tiempo polinomial (en lugar del tiempo O (km) que estaría implicado por un algoritmo k-pass). Vea especialmente la referencia al artículo de Tompa sobre por qué el caso dirigido parece difícil.

Noam
fuente
1
M. Tompa, Dos algoritmos familiares de cierre transitivo que no admiten tiempo polinómico, implementaciones de espacio sublineal , SIAM J. Comput. 11 (1), 130-137. dx.doi.org/10.1137/0211010
András Salamon el
Este documento ofrece "un algoritmo para la conectividad st que se ejecuta simultáneamentesub-lineal espacio y tiempo polinómico".
4

k=Θ(n)O(logn)O(nm)

zotachidil
fuente
3

k

Chad Brewbaker
fuente
Gracias por el puntero, este es un artículo interesante. Los procesadores tienen acceso común a una estructura de datos que es al menos tan grande como el gráfico, por lo que esto no ayuda a reducir el uso de espacio. De hecho, sería interesante si hubiera una manera de reducir el uso del espacio explotando la cantidad de rondas y la cantidad de procesadores.
András Salamon
2

Otra no respuesta: hay algunos documentos sobre algoritmos de estilo mapreduce que operan en gráficos grandes. El objetivo es lograr un espacio por máquina o (m) para gráficos densos, pero generalmente necesita un espacio O (n) por máquina.

theory.stanford.edu/~sergei/papers/soda10-mrc.pdf http://theory.stanford.edu/~sergei/papers/spaa11-matchings.pdf

Martin Pál
fuente
1

O(nlogn/k)kn/kstn/kn/kst

domotorp
fuente