Reduzindo o uso de espaço da st-connectivity com várias passagens?

Suponha que um gráfico com vértices seja apresentado como um fluxo de arestas, mas várias passagens são permitidas no fluxo.n $G$$n$$m$

Monika Rauch Henzinger, Prabhakar Raghavan e Sridar Rajagopalan observaram que o espaço é necessário para determinar se existe um caminho entre dois vértices fornecidos em , se passes são permitidos nos dados. (Consulte também a versão do relatório técnico .) No entanto, eles não fornecem um algoritmo para realmente atingir esse limite. Suponho que um algoritmo ideal realmente ocuparia espaço em um modelo de computação realista, pois é preciso distinguir os vértices diferentes se não for possível indexar a memória usando ponteiros de tamanho constante.G k O ( ( $\Omega(n/k)$$G$$k$$O((n\, \log\, n)/k)$$n$

Como se pode decidir a conectividade gráfica com passes usando espaço?O ( ( $k$$O((n\, \log\, n)/k)$

Se apenas uma passagem for permitida, os dados de entrada poderão ser armazenados como uma partição do conjunto de vértices, mesclando conjuntos se uma aresta for vista entre os vértices em dois conjuntos diferentes. Isso claramente requer no máximo espaço. Minha pergunta é sobre : como alguém pode usar mais passes para reduzir o espaço necessário?k > $O(n\, \log\, n)$$k > 1$

(Para evitar trivialidade, é um parâmetro que não pode ser delimitado a priori por uma constante, e os limites de espaço são expressões que envolvem funções de e .)n $k$$n$$k$

Atualização: mesmo para , seria realmente útil ter uma maneira de armazenar apenas vértices. Ou existe, na verdade, um limite inferior mais forte para alguma constante , independentemente de ?n / 2 c n c $k=2$$n/2$$cn$$c$$k$

É um problema aberto de longa data encontrar um algoritmo para conectividade st que roda simultaneamente no espaço sub-linear e no tempo polinomial, uma tarefa mais fácil do que o que você está buscando. Tais algoritmos são conhecidos pela versão não direcionada , mas mesmo estes requerem um grande tempo polinomial (em vez de O (km), o que seria implícito por um algoritmo k-pass). Veja especialmente a referência ao artigo de Tompa sobre por que o caso direcionado parece difícil.

Esta não é uma resposta, mas eu só queria ressaltar que, se você puder resolver esse problema para , então resolverá a conectividade st no espaço e no tempo ( que, no caso off-line, você pode fazer com probabilidade> 1/2 fazendo uma caminhada aleatória; mas parece um pouco mais difícil quando as bordas vêm de um fluxo). Pergunta muito interessante, IMO.O ( log n ) O ( n m $k = \Theta(n)$$O(\log n)$$O(nm)$

Yossi Shiloach, Uzi Vishkin. Um algoritmo de conectividade paralela O (log n). J. Algorithms, 1982: 57 ~ 67 - Um dos meus trabalhos favoritos. Seria interessante se você pudesse fazê-lo no espaço O ((nlogn / k) / p) com processadores p em rodadas, em que cada rodada a cada processador é permitido apenas ler em O (n / p) das bordas.$k$

Ainda outra não resposta: existem alguns artigos sobre algoritmos do estilo mapreduce que operam em grandes gráficos. O objetivo é obter o espaço por máquina o (m) para gráficos densos, mas normalmente precisa de O (n) espaço por máquina.

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

Também não é uma resposta, mas você pode decidir a conectividade st no espaço não determinístico de com passes. Apenas adivinhe os primeiros nós de um caminho e verifique se eles estão conectados na primeira rodada, continue a partir do último desses vértices e verifique o próximo no caminho e assim por diante.k n / k s t n / k n / k s $O(n\log n/ k)$$k$$n/k$$st$$n/k$$n/k$$st$