Subgrafo que contiene todos los nodos y bordes que forman parte de las rutas st simples de longitud limitada en un dígrafo

8

Nota: publiqué una pregunta similar con respecto al gráfico no dirigido .

Dado

  • Un dígrafo sin múltiples aristas o buclesG
  • Un nodo fuente s
  • Un nodo objetivo t
  • Longitud máxima del camino l

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 .GGGstl

Tenga en cuenta que no necesito enumerar las rutas.

Lior Kogan
fuente
¿Hay más restricciones para su problema? Recuerde que el siguiente problema es NP-completo: Dado el dígrafo y los vértices s , t , v , ¿existe una ruta ( s , t ) que también contenga v ? Gs,t,v(s,t)v
Kristoffer Arnsfelt Hansen
@KristofferArnsfeltHansen, interesante! ¿Le gustaría agregar eso como respuesta y proporcionar una referencia para ese resultado? Parece que responde a la pregunta original en negativo.
DW
@ KristofferArnsfeltHansen: No hay más restricciones.
Lior Kogan

Respuestas:

6

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 .lNPNP

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 ?NPGs,t,v(s,t)v

Kristoffer Arnsfelt Hansen
fuente
¿Cómo encaja con la solución aceptada aquí? stackoverflow.com/questions/10825249/… ¿Es NP-hard justo cuando se dirige el gráfico?
Lior Kogan
1
Correcto, el problema anterior se puede resolver de manera eficiente para la variante cuando el gráfico no está dirigido como se describe en la respuesta a la que se vincula.
Kristoffer Arnsfelt Hansen
0

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 = .)estel=

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 0sy 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 eeEsteGs0s0st1tt1ees 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.ststste

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).

l


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.

DW
fuente
1
Gracias. También mira aquí: stackoverflow.com/questions/10825249/…
Lior Kogan
1
(s,t)NP
0

GO(V+E)

sGds(v)vGsvtG(v,u)(u,v)Gdt(v)vG

vstvds(v)+dt(v)

GvGds(v)+dt(v)l(u,v)ds(u)+dt(v)l1

Mathias Rav
fuente
55
Puede devolver rutas que no son simples (por ejemplo, para el gráfico s <--> a <--> b <--> c <--> t; b <--> d: el nodo d es un callejón sin salida y no debería ser parte de la solución).
Lior Kogan
0

lO(2lm(n+m))l

mle

Foreach $e=(u,v)\in E$: 
a. do for $O(2^l)$ times:
  1. Compute a random partition of the vertices set $V=(S,V\setminus S)$ 
   such that $s,u\in S$, $v,t\not \in S$ (and every other vertex is in $S$ w.p. 1/2).
  2.Find the shortest path from $s$ to $u$ in the subgraph induced by $S$.
    And the shortest path from $v$ to $t$ in the subgraph of $V\setminus S$. 
  3.If the sum of distances is no more than $l-1$, add $e$ to the output graph.


lGe

uSVS2lO(2l)

Desrandomización

2polylog(l)

(n,l)SO(2l+log3(l)poly(n))

RB
fuente