Индуцированный подграф; существование пути между двумя узлами

Question

Извините за стену текста, это настолько кратко, насколько я мог это сделать!

У меня есть один очень большой ориентированный граф G и подмножество вершин S изнутри G. Что янам нужно найти подграф G, индуцированный S, с дополнительным соображением, что если существует некоторый путь между вершиной p и вершиной q в G, то существует ребро между этими двумя вершинами в индуцированном подграфе.Это ключ;она немного сложнее (я думаю), чем обычная проблема с подграфами.

Самый простой способ решения этой проблемы, который я могу придумать, заключается в следующем (я понимаю, что это, вероятно, не самый эффективный, дайте мне знать,если у вас есть другие предложения, которые не являются слишком сложными для реализации): для каждой пары вершин в S проверьте наличие пути между ними в G. Если такой путь существует, вставьте ребромежду p и q в индуцированном подграфе.Для моих целей время n ^ 2 - это не , что плохо.

Итак, я полагаю, у меня есть два вопроса: 1) Какой самый быстрый способ определить, является ли путьСУЩЕСТВУЕТ между двумя вершинами?Мне не нужно знать путь, просто существует он или нет.Кроме того, если есть некоторая предварительная обработка, которую я могу сделать для всего графа, чтобы сделать этот расчет быстрее, что бы это могло быть, так как я должен выполнять этот расчет между каждой парой вершин?

2) Есть ли быстреечем тот, который я предложил, чтобы найти тип индуцированного подграфа, который я описал?

Большое спасибо за помощь!

Answer 1

Проблема нахождения того, существует ли путь между двумя вершинами, называется проблемой транзитивного замыкания, и она так же сложна, как умножение матриц в общем случае.Сначала я бы запустил на вашем графе алгоритм сильно связанных компонентов, чтобы сжать циклы в один узел и сформировать ориентированный граф.Если вам повезет, у вас будет несколько больших циклов, и это облегчит последующую переходную задачу.Затем я запустил алгоритм Флойда Варшалла для всех пар кратчайших путей на этом графе, чтобы вычислить транзитивное замыкание, потому что его код невероятно прост.Возможно, один из алгоритмов умножения матриц o (n ^ 3) будет быстрее, но я сомневаюсь, что он будет намного быстрее, потому что константа очень мала, Флойд Уорссалл.

Вот быстрый алгоритм для сильно связанных компонентов .

И это содержит доказательство эквивалентности умножения матриц и транзитивного замыкания.

Я не уверен, есть ли какой-нибудь хороший способ обойти вычисление транзитивного замыканиячтобы решить вашу первоначальную проблему.Я подозреваю, что нет, но, с другой стороны, иногда умные люди придумывают что-то великое.