Здесь было несколько вопросов ( 1 , 2 , 3 ) о транзитивном завершении, которые заставили меня задуматься, возможно ли что-то подобное:
Предположим, мы получили входной ориентированный граф и хотел бы ответить на запросы типа "? ", т.е. спрашивает, существует ли ребро между двумя вершинами в транзитивном завершении графа ? (эквивалентно, "есть ли путь от в в ? ").
Предположим, что дано вам разрешено выполнять предварительную обработку во времени а затем требуется ответить на запросы вовремя ,
Очевидно, если (т.е. никакая предварительная обработка не разрешена), лучшее, что вы можете сделать, это ответить на запрос вовремя , (запустить DFS из в и верните true, если существует путь).
Другой тривиальный результат заключается в том, что если Вы можете вычислить транзитивное замыкание и затем ответить на вопросы в ,
Как насчет чего-то посередине? Если вам позволят, скажем время предварительной обработки, вы можете отвечать на запросы быстрее, чем ? Может быть, улучшить это, чтобы?
Другой вариант: предположим, у вас есть время предварительной обработки, но только пространство, можете ли вы использовать предварительную обработку, чтобы ответить на запросы более эффективно, чем ?
Можем ли мы вообще сказать что-нибудь о компромисс, который позволяет отвечать на такие запросы?
Несколько похожая структура компромисса рассматривается в системах GPS, где хранение полной таблицы маршрутизации всех парных расстояний между местоположениями невозможно, поэтому используется идея оракулов расстояния, в которой хранится неполная таблица, но допускается значительное ускорение запросов при вычислении расстояния целого график (обычно дает только приблизительное расстояние между точками).
Ответы:
Компактные оракулы достижимости существуют для плоских графиков,
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
источник
Я частично отвечу на ваш вопрос: кажется, есть некоторые причины, по которым такую конструкцию трудно получить.
Предположим, что для любого 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 года.
источник