Найти все * вершины * на всех простых путях между двумя вершинами в неориентированном графе

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

То есть: Учитывая неориентированный граф и две различные вершины, существует ли алгоритм полиномиального времени, который находит каждую вершину, которая находится по крайней мере на одном простом пути между двумя вершинами? Это не такие же, как и для подключения; тупики и тупики исключены. Однако допустимы пути ветвления и соединения.

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

В более общем смысле: Учитывая два непересекающихся множества вершин в графе, существует ли алгоритм полиномиального времени, который находит все вершины, которые лежат на простом пути от вершины в одном множестве до вершины в другом множестве?

(Простите меня, если есть действительно очевидное решение для этого. Конечно, похоже, что должно быть.)

Ответ 1

Ниже приведено детерминированное линейное решение. Вставка края между двумя вашими конечными вершинами (пусть их называют a и b), если такое ребро еще не существует, превращает вашу проблему в задача нахождения максимального набора вершин v, лежащих на любом простом цикле через a и b. Вы можете убедить себя, что такой набор соответствует максимальному подграфу, содержащему a и b, который не может быть отключен удалением любого из его узлов (также называемого биконтекнированной компонентой). Эта страница описывает концепцию и классический алгоритм линейного времени (на основе DFS) Hopcroft и Tarjan для идентификации всех компонентов с бинокшей (вам нужно только один содержит a и b).

Второй вопрос о простых путях между двумя наборами (пусть их называют A и B) может свести к первому вопросу, создав новую вершину a с ребрами ко всем вершинам в и вершину b с ребрами ко всем вершинам в B, а затем решить ваш первый вопрос для a и b.

Ответ 2

Вы не возражаете против вероятностного решения? То есть, это не гарантирует нахождения всех вершин, но обычно это делает сначала попытку и, по всей вероятности, может после двух или трех попыток?

Если вы в порядке с этим, произвольно назначьте каждому ребру сопротивление и решите для напряжения каждого node, если вы положите источник на напряжение 1 и приемник при напряжении 0. Любое ребро, где два узла, соединяющие его с разными напряжениями, явно находятся на простом пути (путь легко построить, просто пройти через восходящее напряжение с одного конца и спуститься с другого). Край, где два узла, соединяющих его с одним и тем же напряжением, крайне маловероятен на простом пути, хотя теоретически это может произойти.

Повторите с несколькими случайно назначенными наборами сопротивлений, и вы, по всей вероятности, найдете все ребра, которые находятся на простых путях. (Вы не доказали этот ответ, но шансы быть неправыми исчезающе малы.)

Конечно, как только вы узнаете все ребра, которые находятся на простых путях, тривиально получить все вершины, которые находятся на простых путях.

Обновление

Я считаю, что следующее верно, но не имеет доказательств. Предположим, что мы берем набор сопротивлений и выстраиваем напряжения. Для каждого ребра, имеющего простой путь, существует другое ребро (возможно, такое же), что изменение сопротивления только этого края приведет к изменению напряжения на первом ребре. Если это так, то в полиномиальное время можно идентифицировать каждое ребро по простому пути.

Интуитивно это имеет смысл для меня, но я понятия не имею, как я это докажу.