Максимальный поток - через вершину - как?

Question

Проблема:

Пусть G = (V, E) - ориентированный граф на n> = 3 вершинах с m ребрами. Набор вершин V включает три специальные вершины a, v и b. Найдите простой путь от a до b через v, если он существует. (Простой путь - это путь без повторяющихся вершин.)

Я считаю, что эту проблему следует / можно решить с помощью алгоритма Max Flow, но я не уверен, как это сделать. Это напоминает мне алгоритм Max Flow с несколькими источниками, где ребра имеют емкость 1. Кто-нибудь знает, как проблема может быть сведена к алгоритму максимального потока?

Если я установлю вершину b как приемник, я не могу быть уверенным, что она будет включать v. Если я установлю v как приемник, как мне продолжить, когда достигается v?

Answer 1

Должно работать следующее:

• найти все минимальные пути от a до v, которые не содержат вершина b. Вы можете получить их с помощью (например) DFS на графе без вершины b. Мы говорим, что a-v -путь p минимален, если никакой другой a-v -путь p' не содержит только вершины из p.

• для каждого минимального a-v -пути, попробуйте найти путь от v до b, игнорируя вершины, уже принадлежащие a-v -путу. Если вы найдете такую ​​вещь, все готово.

Примечание: Обратите внимание, что число путей может расти экспоненциально, но, как я указал в своем комментарии, по крайней мере, обобщенная версия этой проблемы, по-видимому, сводится к TSP, поэтому, вероятно, очень трудно.

Answer 2

Это эквивалентно запросу, если граф содержит подграф, гомеоморфный направленному пути с тремя вершинами (шаблон - это граф на некоторых вершинах входного графа, а подграф гомеоморфен шаблону, если ребрашаблон может быть сопоставлен с простыми попарно непересекающимися путями подграфа). Fortune, Hopcroft и Wyllie доказали, что направленный гомеоморфизм подграфа NP-труден почти для всех фиксированных паттернов, включая этот.Таким образом, проблема NP-трудна и не может быть решена с помощью методов потока, если P = NP.

Ненаправленная версия может быть уменьшена до максимального потока, хотя a и b будут источником и v стоком.