Limite inferior da verificação da conectividade do gráfico no fluxo

Gostaria de verificar o status do limite inferior do espaço para resolver o problema de conectividade no fluxo em passes. O Ω ( n / p ) foi declarado na literatura, mas parece ser um problema ligeiramente diferente. Perdi alguma coisa? Detalhes abaixo. $p$$\Omega(n/p)$

Dado um gráfico de n vértices em um fluxo (as arestas são apresentadas uma a uma de maneira fluida), queremos verificar se G está conectado. Qual é o espaço mínimo que um algoritmo precisa para resolver esse problema quando é permitido ler o fluxo para p passa?$G$$n$$G$$p$

Feigenbaum et al . mostrou espaço para algoritmos de uma passagem para uma classe de problemas que inclui esse problema (consulte a Seção 5.1) e afirmou que o limite inferior do espaço Ω ( n / p ) para conectividade foi provado por Henzinger et al. . No entanto, o único limite inferior para o problema de "conectividade" é realmente para o problema de " s - t conectividade": dados os vértices s e t , queremos verificar se s e $\Omega(n)$$\Omega(n/p)$$s$$t$$s$$t$$s$$t$estão no mesmo componente conectado (Teorema 6). A prova disso não pode ser usada para o problema de conectividade, pois pode haver muitos vértices incidentes sem margem.

Então, minha pergunta é, para a versão específica de conectividade que afirmei, existe algum limite inferior conhecido pelo fluxo -pass?$p$

Aqui está uma redução do Disjointness que pode funcionar:

Dados os vetores de bits de entrada x e y , Alice e Bob desejam criar os conjuntos de arestas E 1 e E 2 para um gráfico G, de modo que G seja conectado se não houver um índice tal que x i = y i = 1 .$n$$x$$y$$E_1$$E_2$$G$$G$$x_i = y_i = 1$

O gráfico terá o conjunto de vértices 0 , 1 , … , n × 0 , 1 . Para i < n , Alice adiciona a aresta ( ( i - 1 , 0 ) , ( i , 0 ) ) a E 1 iff x i = 0 ; Da mesma forma, Bob adiciona a aresta ( ( i - 1 , 1 ) , ( $G$${0,1,\ldots,n} \times {0,1}$$i < n$$((i-1,0),(i,0))$$E_1$$x_i = 0$ para E 2 sse y i = 0 . Além disso, Alice adiciona todas as arestas do formulário ( ( i , 0 ) , ( i , 1 ) ) para i ∈ 0 , … , n .$((i-1,1),(i,1))$$E_2$$y_i = 0$$((i,0),(i,1))$$i\in {0,\ldots,n}$

Eu acho que este gráfico tem um componente conectado se if estiver conectado a ( n , 0 ) , o que acontece se for para cada i ∈ 1 , 2 , … , n , x i ou y i for 0; isto é, as duas entradas são separadas.$(0,0)$$(n,0)$$i\in{1,2,\ldots,n}$$x_i$$y_i$

Um menor melhor ligado quando $p=1$ é bits, em que log = log 2 . (A 3 / 2 prazo pode ser feita de forma arbitrária perto de 1 para suficientemente grande n , e assintoticamente é registo log e - registo e ≈ 0,91 ).$n \log n - n (\log \log n + 3/2)$$\log = \log_2$$3/2$$1$$n$$\log\log e - \log e \approx 0.91$

Também se pode aplicar uma redução direta de um jogo de comunicação de conectividade gráfica para obter um limite inferior menos explícito . No entanto, como o fator constante implícito se refere ao número de blocos garantidos pelo Regularity Lemma de Szemerédi , parece acabar tão pequeno que é inútil para aplicações.$\Omega(n \log n)$

Portanto, um limite inferior mais preciso para o caso pass é $p$. Continuo não convencido de que esse seja o verdadeiro limite inferior, uma vez quealcançar tal limite parece improvável- a verdadeira dependência depparece ser mais fraca que uma proporção inversa. No entanto, o limite deve ser pelo menosΩ($\frac{1}{p}(n\log n - n(\log\log n + 3/2))$$p$, melhorandoΩ(n/p).$\Omega(\frac{1}{p}n\log n)$$\Omega(n/p)$