Encontrar al menos dos caminos de la misma longitud en un gráfico dirigido

20

Supongamos que tenemos un grafo dirigido y dos nodos y . Me gustaría saber si ya hay algoritmos para calcular el siguiente problema de decisión:G=(V,E)AB

¿Hay al menos dos caminos entre y de la misma longitud?AB

¿Qué tal la complejidad? ¿Puedo resolverlo en tiempo polinómico?


Me gustaría agregar una nueva restricción en el gráfico, tal vez el problema sea más solucionable. En la matriz de adyacencia, cada columna no está vacía. Entonces, cada nodo tiene al menos una flecha en la entrada y también hay al menos un nodo conectado a sí mismo. Entonces, si el nodo es el -ésimo nodo, entonces es un borde en el gráfico.i(i,i)

Paolo Parisen T.
fuente
¿Te refieres a senderos simples? (visitando cada nodo como máximo una vez), ¿también se les permite tener un nodo interno común?
1
no, no hay restricciones en los caminos. puedes hacer un bucle, si quieres.
Paolo Parisen T.
La observación fácil es esta: si solo hay una ruta simple entre , y esta ruta simple está conectada como máximo a un bucle, simplemente podría decir , si hay al menos dos bucles de diferente longitud conectados a esta ruta simple , podrías decir que sí ... (creo que cosas similares son útiles y podrías probarlo), pero en el caso de rutas simples disjuntas (si durante la prueba de esto encontraste rutas simples disjuntas), es NPC. N oA,BNo
1
@mrm: No veo esto como un duplicado. Pedir todas las caminatas es una operación que consume mucho tiempo (en general, hay un número infinito de caminatas), mientras que el OP solicita dos rutas (simples), no todas las caminatas.
Dave Clarke

Respuestas:

10

Considere un gráfico , queremos saber si hay dos caminos diferentes de a de la misma longitud. ¿Qué hacer? Simple: codifique dos caminos en uno. Defina el gráfico con vértices . Haces un paso en al hacer dos pasos independientes en . El bit adicional le dice si las dos rutas ya se han separado entre sí.A B G V × V × { 0 , 1 } G GGABGV×V×{0,1}GG

Formalmente, hay una arista en iff , en y .G i i j j G e = e ( i , i ) ( j , j )(i,j,e)(i,j,e)GiijjGe=e(i,i)(j,j)

El algoritmo verifica si hay una ruta a en , que es , o algo así como .(A,A,0)(B,B,1)GO(V4)O((V+E)2)

Si acepta que este algoritmo es correcto, entonces, como consecuencia, la ruta en tiene una longitud máxima de , por lo tanto, las posibles "colisiones de ruta" deben ocurrir más tarde en esa longitud. Puede obtener un algoritmo partir de esta observación, donde es la complejidad de la multiplicación de matrices (pregunte si necesita un spoiler ...).G2n2O(VωlogV)ω

Creo firmemente que hay un algoritmo , que utiliza más de la estructura del problema.O(V+E)

sdcvvc
fuente
3
Eso es elegante
Raphael
4

Probablemente tengo una respuesta para este problema, pero no estoy seguro de que funcione.

No es importante "encontrar" los dos caminos, lo único importante es "saber" si existen o no. No creo que este sea un problema NP completo.

Por lo tanto, tomar la matriz de adyacencia . Podemos suponer fácilmente que está lleno de valor 0,1. (0 = sin borde; 1 = hay un borde) Usemos el siguiente álgebra con 3 valores (0,1,2), donde todo funciona como de costumbre excepto: 2 + <algo> = 2 ; 2 <lo que sea mayor que 0> = 2A2+<something>=22<whatever greater than 0>=2

Entonces, si hay dos caminos de la misma longitud desde , espero que haya un valor p tal que ( A p ) i , j = 2 .i,jp(Ap)i,j=2

Sea el número de vértices en el gráfico (o, digamos, que A tiene dimensión n × n ). No sé el valor de p , pero si itero A multiplicando consigo mismo como máximo n 2, debería encontrar la respuesta. (entonces, p < n 2 ) (el sentido es que verifico A , luego verifico A 2 , luego verifico A 3 y así sucesivamente ...)nAn×npAn2p<n2AA2A3

Aquí está mi argumentación:

  • si los dos caminos son sencillos, bueno, funciona; si los hay, a lo sumo tengo que iterar veces.n
  • Si hay al menos un ciclo nuevo o hay una ruta con dos ciclos, bueno, tengo que encontrar el mínimo común múltiplo (LCM). es un valor mayor seguro y en menos de n 2 veces, si es que debería tener que encontrarlos.n2n2
  • Si los dos caminos son dos caminos distintos, ambos con un ciclo, entonces es más o menos similar a encontrar una solución para esto dos ecuación: , donde m y k son la longitud de estos dos distintos ciclos La multiplicación de la matriz A q , como se definió anteriormente, dice "¿hay una ruta de i a j cuya longitud es q ?" Entonces, si A q es mayor que 1 , significa que hay más caminos que conducen de i a j . Al iterar la matriz nα+βm=γ+δkmkAqijqAq1ij veces pasamos por todas las combinaciones posibles de δ y β . De hecho, L C M ( a , b ) se define como ( a b ) / G C D ( a , b ) y ningún ciclo puede ser mayor que n .n2δβLCM(a,b)(ab)/GCD(a,b)n

Me detengo para iterar una vez que encontré .(Ap)i,j=2

¿Me equivoco?

Paolo Parisen T.
fuente
Intenté lo mismo y encontré algunos problemas / incertidumbres: 1) ¿Qué pasa si las rutas están conectadas a más de un ciclo? ¿Tiene que "verificar" todas las combinaciones (en el peor de los casos, cada nodo se encuentra en muchos ciclos exponencialmente), explotando el límite superior, o es suficiente considerar solo uno para cada uno? 2) Debido a las constantes compensaciones y γ , ¿el LCM es realmente un límite superior? αγ
Raphael
Por cierto, no hay necesidad de un álgebra funky: simplemente deténgase en el momento en que calcule un como entrada de matriz. 2
Raphael
@Raphae 1) si hay una ruta con dos ciclos, entonces seguramente hay dos rutas de la misma longitud. uno que se repite en el primer ciclo y otro que se repite en el segundo. ¿Cuánto tienen que recorrer? exactamente el MCM de la longitud de ambos ciclos. esto está delimitado por , donde n es el número de vértices en el gráfico. 2) LCM es el límite superior (en el caso 1)) porque LCM (a, b) está limitado por a * b más compensaciones α y γ ; entonces, en total tenemos L C M ( a , b ) + α + γ < a b + α + γn2nαγLCM(a,b)+α+γ<ab+α+γ. sabemos que , entonces a b + α + γ es menor que n 2 . α+γ+a+b<nab+α+γn2
Paolo Parisen T.