Réduire l'utilisation de l'espace de st-connectivité avec plusieurs passes?

20

Supposons qu'un graphe à sommets soit présenté comme un flux de arêtes, mais plusieurs passes sont autorisées sur le flux. $G$ $n$ $m$

Monika Rauch Henzinger, Prabhakar Raghavan et Sridar Rajagopalan ont observé que l' espace est nécessaire pour déterminer s'il existe un chemin entre deux sommets donnés dans , si passes sont autorisées sur les données. (Voir aussi la version du rapport technique .) Cependant, ils ne fournissent pas d'algorithme pour réellement atteindre cette limite. Je suppose qu'un algorithme optimal prendrait en fait $\Omega(n/k)$ $G$ $k$ espace dans un modèle informatique réaliste, car il faut distinguer les sommets différents si l'on ne peut pas indexer la mémoire à l'aide de pointeurs de taille constante. $O((n\, \log\, n)/k)$ $n$

Comment décider de la connectivité d'un graphe avec passes en utilisant $k$ espace? $O((n\, \log\, n)/k)$

Si un seul passage est autorisé, les données d'entrée peuvent être stockées en tant que partition de l'ensemble de sommets, fusionnant les ensembles si une arête est vue entre les sommets de deux ensembles différents. Cela nécessite clairement au plus espace. Ma question porte sur : comment utiliser plus de passes pour réduire l'espace requis? $O(n\, \log\, n)$ $k > 1$

(Pour éviter la trivialité, est un paramètre qui ne peut pas être limité a priori par une constante, et les limites d'espace sont des expressions impliquant des fonctions à la fois de et de .) $k$ $n$ $k$

Mise à jour: même pour il serait vraiment utile d'avoir un moyen de stocker uniquement sommets. Ou existe-t-il réellement une borne inférieure plus forte pour une constante , indépendamment de ? $k=2$ $n/2$ $cn$ $c$ $k$

reference-request graph-algorithms ds.data-structures lower-bounds data-streams András Salamon
la source

Comment indépendamment de

? S'il peut être très grand, alors la connectivité st peut être résolue dans l' espace

, donc il y a une chance pour un algorithme, mais comme le montre azotlichid, probablement pas dans

.

k

$k$

O (\log^{2} n)

$O(\log^2 n)$

O (n \log n / k)

$O(n\log n /k)$

domotorp

Notez que l'élimination des passes de Guha et McGregor pour les algorithmes randomisés fonctionne dans la direction opposée, en utilisant plus d'espace pour autoriser moins de passes (bien que l'espace supplémentaire soit grand si l'erreur souhaitée est petite). Cette question demande si en utilisant plus de passes, on peut réduire l'utilisation de l'espace.

András Salamon

8

C'est un problème ouvert de longue date que de trouver un algorithme de st-connectivité qui s'exécute simultanément dans un espace sub-linéaire et un temps polynomial, une tâche plus facile que ce que vous visez. De tels algorithmes sont connus pour la version non dirigée , mais même ceux-ci nécessitent un temps polynomial important (plutôt qu'un temps O (km) qui serait impliqué par un algorithme à k-passes). Voir en particulier la référence au document de Tompa sur les raisons pour lesquelles le cas dirigé semble difficile.

Noam
la source

1

M. Tompa, Deux algorithmes familiers de fermeture transitive qui n'admettent pas de temps polynomial, implémentations d'espace sublinéaire , SIAM J. Comput. 11 (1), 130–137. dx.doi.org/10.1137/0211010

András Salamon

Cet article donne "un algorithme de st-connectivité qui s'exécute simultanément

$\hspace{1.71 in}$ l' espace sous-linéaire et polynomiale ».

4

$k = \Theta(n)$ $O(\log n)$ $O(nm)$

zotachidil
la source

3

$k$

Chad Brewbaker
la source

Merci pour le pointeur, c'est un article intéressant. Les processeurs ont un accès commun à une structure de données au moins aussi grande que le graphique, ce qui n'aide pas à réduire l'utilisation de l'espace. Il serait en effet intéressant qu'il existe un moyen de réduire l'utilisation de l'espace en exploitant le nombre de tours ainsi que le nombre de processeurs.

András Salamon

2

Encore une autre non-réponse: il existe des articles sur les algorithmes de style mapreduce fonctionnant sur de grands graphes. L'objectif est d'obtenir un espace par machine o (m) pour les graphiques denses, mais nécessite généralement un espace O (n) par machine.

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

Martin Pál
la source

1

$O(n\log n/ k)$ $k$ $n/k$ $st$ $n/k$ $n/k$ $st$

domotorp
la source

Réduire l'utilisation de l'espace de st-connectivité avec plusieurs passes?

Réponses: