Проверьте, существует ли путь между двумя вершинами в ориентированном ациклическом графе - запросы

Question

Этот вопрос может быть легко решен в O (n + m) для каждого запроса, однако возможно ли это ответить на такие запросы с лучшей сложностью с предварительной обработкой лучше, чем O (n²)?

В дереве это можно легко сделать, работая с предварительным заказом и в порядке. Я пробовал что-то подобное в DAG, но это не имеет никакого смысла.

Я также попытался изменить эту проблему в LCA в проблеме DAG, но поиск LCA в DAG не может быть решена достаточно быстро.

---

Чтобы быть точным с ограничениями, скажем:

п - число вершин, до 10^5

м - число ребер, до 10^5

д - количество запросов, до 10^5

Answer 1

Интересный вопрос. Моя интуиция говорит «нет». Хотя я не думал об этом.

Однако (при условии, что этот вопрос не является теоретическим), для практических целей вы можете использовать Bloom filter.

Одно из возможных решений вашей проблемы с использованием фильтра Блума должно сначала генерировать K разных порядков графика, а для каждого - сохранять сопоставление от узла к его индексу в этом порядке. Затем, чтобы проверить «достижимость» от N1 до N2, вы проверяете (порядок foreach), если индекс-N1 меньше индекса-N2 (эта проверка равна O (1)). Если это справедливо для всех ордеров, то это достигается с довольно хорошей вероятностью (assuming K is big enough). (В зависимости от вашего случая использования в реальном мире, возможно, даже будет нормально переносить такие ложные срабатывания, или вы можете запустить надежную проверку O (N + M)). Иначе это определенно не так.

Answer 2

У меня такое ощущение, что может быть решение по следующим строкам, но это далеко не полное решение.

Пусть S - подмножество вершин. Для каждой вершины V в графе рассмотрим множество D_S (V), которое я определяю следующим образом: D_S (V) = {V}, если V в S, и в противном случае D_S (V) является объединением {V} с множества D_S (W) для всех прямых потомков W из V. (То есть, это «все возможные потомки V, но останавливайте рекурсию всякий раз, когда вы нажимаете на элемент V».) Вопрос в том, можем ли мы найти набор S такой, что размер S равен O (f (N)), а также D_S (V) имеет размер O (g (N)) для всех V и где f и g асимптотически сублинейны? (Может быть, мы можем достигнуть sqrt для обоих, например.)

Если мы сможем это найти, то предлагаю следующую стратегию. Для предварительной обработки создайте для каждого U в S хеш-таблицу, содержащую все вершины, в конечном итоге доступные из U. Это может быть достигнуто в O (f (N) * M); это не обязательно лучше, чем O (N^2), но лучше, чем O (M * Q), по крайней мере.

Теперь, чтобы ответить на запрос «является достижимым из V?», Это тривиально, если V в S. В противном случае мы проверяем, является ли V = U, и в этом случае это также тривиально. Наконец, мы применяем тот же процесс ко всем потомкам V, рекурсивно, возвращая «да», если ответ «да» через один из двух случаев выше, но «нет», только если мы никогда не находим U. Эта рекурсия занимает O (g (N)).

Остается вопрос о том, как выбрать S. Я думаю, что если граф возникает из какого-то процесса, где внешняя степень следует степенному закону, можно просто взять вершины sqrt (N) с наивысшей степенью.Но, например, если у нас есть граф на N = 2 * K вершин (i, 0) и (i, 1), с K^2 ребрами: от каждого (i, 0) до каждого (j, 1); то нет подходящего подмножества S. Но, может быть, графики, которые не имеют подходящего S, по необходимости нуждаются в некоторой степени однородности, которую мы можем использовать ... Или, может быть, нет. Я не знаю. Любые идеи, дайте мне знать!