¿Cuáles son las obstrucciones para extender

Prueba de Omer Reingold que da un algoritmo para USTCON (En un T ndirected gráfico con vértices especiales y , son Con TARSE?) Utilizando sólo logspace. La idea básica es construir un gráfico expansor a partir del gráfico original, y luego hacer el recorrido en el gráfico expansor. El gráfico expansor se realiza cuadrando el gráfico original muchas veces logarítmicamente. En el gráfico expansor, el diámetro es solo logarítmico, por lo que es suficiente una búsqueda DFS de profundidad logarítmica. $L=SL$ $s$ $t$

Extendiendo el resultado a implicaría la existencia de un algoritmo de logspace para DSTCON - la misma, pero para D irected gráficos. (A veces solo STCON.) Mi pregunta, tal vez un poco blanda, es ¿cuáles son las principales obstrucciones para extender la prueba de Reingold a eso? $L=NL$

Parece un poco como si hubiera una especie de gráfico de "expansor dirigido". Un tipo similar de construcción, donde se agregan los bordes correspondientes a los caminos dirigidos de longitud media, y luego algunos correspondientes a los largos; y luego puede atravesar el gráfico con profundidad logarítmica moviéndose a través de caminos cortos para llegar a uno largo; luego de vuelta a los caminos cortos al final.

¿Hay una falla importante en este concepto? ¿O es que no hay buenas construcciones de tales expansores? ¿O de alguna manera requiere más memoria que la versión no dirigida?

Desafortunadamente, no puedo encontrar mucho en gráficos de expansión dirigida. De hecho, esencialmente todo lo que pude encontrar fue /math/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution (que no tiene respuesta) y https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers . ¿Hay un término diferente en el que debería estar buscando?

graph-algorithms nondeterminism expanders logspace Alex Meiburg
fuente

Este artículo da una idea de cómo extender

L = S L

$L=SL$

:people.seas.harvard.edu/~salil/research/regular-abs.html

L = R L

$L=RL$

sdcvvc

Ver punto 3. aquí . Puede objetar que es una especulación completa, pero observe que la respuesta de Scott básicamente hace el mismo punto sobre la exploración aleatoria de gráficos dirigidos.

Thomas Klimpel

$n$ $t$ $s$ $s$ $t$ $2^n$ $USTCON$ $RL=NL$ $L=NL$ $O(\log^2 n)$

Scott Aaronson
fuente

El tipo de algoritmo que describiría sería, más o menos, bueno, ejecutas la operación de "cuadrado y zig-zag" de Reingold varias veces para comenzar. Supongo que la modificación sería que, en lugar del cuadrado que contiene solo rutas de longitud 2 en el gráfico original, incluye rutas de longitud 1 y 2. Intente todas las secuencias logarítmicamente profundas, como la suya. Si numeramos los vértices de su gráfico como 1, 2, .. n, entonces el primer gráfico 'cuadrado' conecta 1 a 2 y 3, el siguiente 'cuadrado' lo conecta a 2345, etc. Los pasos en zig-zag mantienen grados bajo. Obviamente duro, pero no veo por qué falla.

Alex Meiburg

\frac{n}{2^{Θ (\sqrt{\log n})}}

$\frac{n}{2^{\Theta(\sqrt{\log n})}}$

\frac{n}{2^{Θ (\sqrt{\log n})}}

$\frac{n}{2^{\Theta(\sqrt{\log n})}}$

\log n

$\log n$

¿Cuáles son las obstrucciones para extender

Respuestas: