Вычисление транзитивного оракула завершения / существования пути

9

Здесь было несколько вопросов ( 1 , 2 , 3 ) о транзитивном завершении, которые заставили меня задуматься, возможно ли что-то подобное:

Предположим, мы получили входной ориентированный граф G и хотел бы ответить на запросы типа "(u,v)G+? ", т.е. спрашивает, существует ли ребро между двумя вершинами в транзитивном завершении графа G? (эквивалентно, "есть ли путь отu в v в G? ").

Предположим, что дано G вам разрешено выполнять предварительную обработку во времени f(n,m) а затем требуется ответить на запросы вовремя g(n,m),

Очевидно, если f=0 (т.е. никакая предварительная обработка не разрешена), лучшее, что вы можете сделать, это ответить на запрос вовремя g(n)=Ω(n+m), (запустить DFS изu в v и верните true, если существует путь).

Другой тривиальный результат заключается в том, что если f=Ω(min{nm,nω})Вы можете вычислить транзитивное замыкание и затем ответить на вопросы в O(1),

Как насчет чего-то посередине? Если вам позволят, скажемf=n2 время предварительной обработки, вы можете отвечать на запросы быстрее, чем O(m+n)? Может быть, улучшить это, чтобыO(n)?

Другой вариант: предположим, у вас есть poly(n,m) время предварительной обработки, но только o(n2) пространство, можете ли вы использовать предварительную обработку, чтобы ответить на запросы более эффективно, чем O(n+m)?

Можем ли мы вообще сказать что-нибудь о f,g компромисс, который позволяет отвечать на такие запросы?

Несколько похожая структура компромисса рассматривается в системах GPS, где хранение полной таблицы маршрутизации всех парных расстояний между местоположениями невозможно, поэтому используется идея оракулов расстояния, в которой хранится неполная таблица, но допускается значительное ускорение запросов при вычислении расстояния целого график (обычно дает только приблизительное расстояние между точками).

RB
источник
Расстояние Хэмминга между двумя узлами i а также j может достичь в tхмель может быть более информативным показателем.
Чад Brewbaker

Ответы:

6

Компактные оракулы достижимости существуют для плоских графиков,

Mikkel Thorup: компактные оракулы для достижимости и приблизительных расстояний в планарных орграфах . J. ACM 51 (6): 993-1024 (2004)

но "трудно" для общих графов (даже разреженных графов)

Михай Патраску: объединение ландшафта клеточных зондов . SIAM J. Comput. 40 (3): 827-847 (2011)

Тем не менее, существует алгоритм, который может вычислять метки, близкие к оптимальным

Эдит Коэн, Эран Гальперин, Хаим Каплан, Ури Цвик: Запрашиваемость и дистанционные запросы через 2-хоповые метки . SIAM J. Comput. 32 (5): 1338-1355 (2003)

Максим А. Бабенко, Эндрю В. Гольдберг, Анупам Гупта, Вишванат Нагараджан: Алгоритмы оптимизации меток узлов . ICALP 2013: 69-80

Опираясь на работу Cohen et al. и другие, есть немало прикладных исследований (сообщество баз данных), см., например,

Руоминг Джин, Гуань Ван: простой, быстрый и масштабируемый доступ к Oracle . PVLDB 6 (14): 1978-1989 (2013)

Yosuke Yano, Takuya Akiba, Yoichi Iwata, Yuichi Yoshida: Быстрые и масштабируемые запросы достижимости на графиках с помощью сокращенной маркировки с ориентирами и путями . CIKM 2013: 1601-1606

Кристиан Соммер
источник
4

Я частично отвечу на ваш вопрос: кажется, есть некоторые причины, по которым такую ​​конструкцию трудно получить.

Предположим, что для любого n-узлового ориентированного графа m-ребра вы можете предварительно обработать его за время T (m, n), чтобы на запросы достижимости можно было ответить за время q (m, n). Затем, например, вы можете найти треугольник в графе m-ребра с n-узлами вT(O(m),O(n))+nq(O(m),O(n))время. следовательноT(m,n)=O(n2) а также q(m,n)=O(n)будет означать прорыв результат. Лучший алгоритм, который мы имеем для поиска треугольников, работает вO(nω) время и неясно, ω=2,

Чтобы увидеть сокращение, предположим, что мы хотим найти треугольник в некотором графе G, Построить 4-слойный график на 4 набораn узлы каждый X,Y,Z,W где каждый оригинальный узел v в G имеет копии vX,vY,vZ,vW, Теперь для каждого края(u,v) в G добавить направленные края (uX,vY),(uY,vZ),(uZ,vW), Это завершает график. Теперь сделайте предварительную обработку вT(O(m),O(n)) время, и задайте вопросы о vX,vW для каждого v,

Вероятно, с некоторой дополнительной работой можно изменить сокращение, чтобы также перечислить треугольники в графе (в настоящее время он перечисляет только узлы в треугольниках). Если можно сделать это эффективно, то, возможно, можно получить некоторую условную нижнюю границу на основе 3SUM, требующейn2+o(1) время, а также, используя результат Патраску от 2010 года.

Virgi
источник