Flujo máximo - a través de vértice - ¿cómo?

Question

El problema:

Sea G = (V, E) un gráfico dirigido en n> = 3 vértices con m bordes. El conjunto vértice V incluye tres vértices especiales a, v y b. Encuentre una ruta simple de aa b por v si existe. (Un camino simple es un camino sin vértices repetidos.)

Creo que este problema debería/puede resolverse con un algoritmo de flujo máximo, pero no estoy seguro de cómo. Me recuerda a un algoritmo de flujo máximo con múltiples fuentes donde los bordes tienen capacidad 1. ¿Alguien sabe cómo se puede reducir el problema al algoritmo de flujo máximo?

Si configuro vertex b como sink no puedo estar seguro de que incluya v. Si configuro v como sink, ¿cómo continúo cuando v se alcanza?

Answer 1

El siguiente debería funcionar:

• encontrar todos mínimos caminos a-v, que no contienen vértice b. Puede obtenerlos mediante (por ejemplo) un DFS en el gráfico sin el vértice b. Decimos que un a-v -path p es mínimo, si ningún otro a-v -path p' contiene solo vértices de p.

• para cada a-v -path mínimo, tratar de encontrar un camino desde v a b vértices haciendo caso omiso de que ya pertenece a la a-v -path. Si encuentras tal cosa, has terminado.

Observación: Tenga en cuenta que el número de caminos podría crecer exponencial, pero como he señalado en mi comentario, al menos la versión generalizada de este problema parece ser reducible a la TSP, siendo por lo tanto probablemente muy difícil.

Answer 2

Esto es equivalente a preguntar si un gráfico contiene un subgráfico homeomórfico a una ruta dirigida con tres vértices (un patrón es un gráfico en algunos vértices del gráfico de entrada, y un subgráfico es homeomorfo a un patrón si los bordes de el patrón se puede mapear a sendas disjuntas de vértices sencillos en pares del subgrafo). Se ha demostrado por Fortune, Hopcroft, and Wyllie que el homeomorfismo subgráfico dirigido es NP-hard para casi todos los patrones fijos, incluido este. Entonces el problema es NP-hard, y no puede ser resuelto por técnicas de flujo a menos que P = NP.

Sin embargo, la versión no dirigida se puede reducir al flujo máximo teniendo a y b como fuente y v sumidero.