Сокращение использования пространства st-подключения с несколькими проходами?

Предположим, что граф с вершинами представлен как поток из ребер, но допускается несколько проходов по потоку.н $G$$n$$m$

Моника Раух Хензингер, Прабхакар Рагхаван и Шридар Раджагопалан отметили, что пространство необходимо, чтобы определить, существует ли путь между двумя заданными вершинами в , если для данных разрешено проходов. (См. Также версию технического отчета .) Однако они не предоставляют алгоритм для фактического достижения этой границы. Я предполагаю, что оптимальный алгоритм фактически будет занимать пространство в реалистичной вычислительной модели, поскольку нужно различать различных вершин, если нельзя индексировать память, используя указатели постоянного размера.G $\Omega(n/k)$$G$$k$$O((n\, \log\, n)/k)$$n$

Как можно решить связность графа с проходами, используя пространство ?O ( ( $k$$O((n\, \log\, n)/k)$

Если разрешен только один проход, входные данные могут быть сохранены как разделение набора вершин, объединяя наборы, если грань видна между вершинами в двух разных наборах. Это явно требует не более пространства. Мой вопрос о : как можно использовать больше проходов, чтобы уменьшить требуемое пространство?k > $O(n\, \log\, n)$$k > 1$

(Во избежание тривиальности является параметром, который не может быть ограничен априори константой, а границы пространства являются выражениями, включающими функции как и .)н $k$$n$$k$

Обновление: даже для было бы действительно полезно иметь способ хранить только вершин. Или на самом деле существует более сильная нижняя граница для некоторой константы , независимо от ?n / 2 c n c $k=2$$n/2$$cn$$c$$k$

Это давняя открытая проблема - найти алгоритм для st-связности, который работает одновременно в сублинейном пространстве и полиномиальном времени, более легкая задача, чем та, к которой вы стремитесь. Такие алгоритмы известны для ненаправленной версии , но даже они требуют большого полиномиального времени (а не O (км) времени, которое подразумевается алгоритмом k-pass). См. Особенно ссылку на статью Томпы о том, почему направленный случай кажется трудным.

Это не ответ, но я просто хотел отметить, что если вы можете решить эту проблему для , то вы решите st-связность в пространстве и времени ( что в автономном случае вы можете сделать с вероятностью> 1/2, выполняя случайное блуждание, но это кажется немного сложнее, когда края приходят из потока). Очень интересный вопрос, ИМО.O ( log n ) O ( n m $k = \Theta(n)$$O(\log n)$$O(nm)$

Йосси Шилоах, Узи Вишкин. Алгоритм параллельного подключения O (log n). J. Algorithms, 1982: 57 ~ 67 - одна из моих любимых работ. Было бы интересно, если бы вы могли сделать это в O ((nlogn / k) / p) пространстве с p процессорами в раундах, где каждый раунд каждому процессору разрешено читать только в O (n / p) ребер.$k$

Еще один не ответ: есть некоторые статьи об алгоритмах в стиле mapreduce, работающих на больших графах. Цель состоит в том, чтобы получить для каждой машины пространство o (m) для плотных графиков, но обычно требуется O (n) пространства на машину.

Теория.stanford.edu/~sergei/papers/soda10-mrc.pdf http://theory.stanford.edu/~sergei/papers/spaa11-matchings.pdf

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