Nota: publiqué una pregunta similar con respecto al gráfico no dirigido .
Dado
- Un dígrafo sin múltiples aristas o bucles
- Un nodo fuente
- Un nodo objetivo
- Longitud máxima del camino
Busco - A subgrafo de G que contiene cualquier nodo y cualquier borde en G (y sólo aquellos), que son parte de al menos un camino simple de s a t con longitud ≤ l .
Tenga en cuenta que no necesito enumerar las rutas.
graph-algorithms
Lior Kogan
fuente
fuente
Respuestas:
Como se plantea la pregunta, teniendo como parte de la entrada, el problema es N P -hard. Esto sigue como un caso especial de la clasificación de la clase de patrones para los cuales el problema de homeomorfismo del subgrafo dirigido es N P -completado por Fortune, Hopcroft y el documento de Wyllie: El problema del homeomorfismo del subgrafo dirigido .l NP NP
En particular, el siguiente problema es -completo: Dado un gráfico dirigido G y vértices s , t , v , ¿existe una ruta (simple) ( s , t ) a través de v ?NP G s,t,v (s,t) v
fuente
Actualización: esta respuesta parece ser defectuosa. Ver el comentario de Kristoffer Arnsfelt Hansen.
No sé cómo resolver su problema, pero aquí hay una técnica para resolver una versión más simple de su problema: a saber, dado un borde , pruebe si existe algún camino simple de s a t que incluya el borde e . (Esto corresponde al caso especial de su problema donde l = ∞ .)e s t e l=∞
Puede resolver este problema más simple usando "flujo máximo con límites inferiores" como una subrutina. En el problema estándar de flujo máximo, la capacidad de cada borde nos da un límite superior en la cantidad de flujo que pasa a través de ese borde, y requerimos que la cantidad de flujo en el borde sea inferior en 0. En "flujo máximo con límites inferiores ", podemos especificar un límite inferior y un límite superior en la cantidad de flujo a través de ese borde. Se sabe que el "flujo máximo con límites inferiores" se puede resolver en tiempo polinómico.
Ahora, supongamos que tenemos una arista , y queremos probar si existe una ruta simple de s a t que incluya la arista e . Vamos a configurar un flujo máximo con un problema de límites inferiores. En particular, tome el gráfico G y agregue un nuevo nodo s 0 con borde s 0 → sy un nuevo nodo t 1 con borde t → t 1 . Haga la capacidad (límite superior) en cada borde 1. El límite inferior en todos los bordes será 0, excepto que el límite inferior en el borde ee∈E s t e G s0 s0→s t1 t→t1 e es 1. Ahora verifique si existe un flujo factible de a t que satisfaga todos los límites (esta prueba se puede hacer en tiempo polinómico, como se mencionó anteriormente). Si no hay flujo, entonces no hay ningún camino simple de s a t . Si hay tal un flujo, a continuación, trazando que el flujo se obtiene un camino simple de s a t que incluye borde e , por lo que sí existe tal camino simple.s t s t s t e
Aprendí esta idea del siguiente artículo:
(Asegúrese de leer la versión del informe técnico, no la versión publicada. Esta idea se encuentra en el segundo párrafo de la introducción).
Alternativamente, podríamos resolver su problema de manera directa utilizando la programación lineal de enteros (ILP). En la práctica, los solucionadores de ILP son bastante buenos en muchos problemas. Sin embargo, su tiempo de ejecución en el peor de los casos sigue siendo exponencial, por lo que esto no va a dar un algoritmo con el tiempo de ejecución polinómico en el peor de los casos. Avíseme si desea que elabore sobre cómo formular esto usando ILP.
fuente
fuente
Desrandomización
fuente