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

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

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

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

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

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