Hay un algoritmo polinomial fácil para decidir si hay una ruta entre dos nodos en un gráfico dirigido (solo haga un recorrido de rutina del gráfico con, por ejemplo, búsqueda de profundidad primero).
Sin embargo, parece que, sorprendentemente, el problema se vuelve mucho más difícil si en lugar de probar la existencia queremos contar el número de caminos.
Si permitimos que las rutas reutilicen los vértices, entonces hay una solución de programación dinámica para encontrar el número de rutas de s a t con n aristas. Sin embargo, si solo permitimos rutas simples, que no reutilizan vértices, la única solución que se me ocurre es la enumeración de la fuerza bruta de las rutas , algo que tiene una complejidad de tiempo exponencial.
Entonces pregunto,
- ¿Es difícil contar el número de caminos simples entre dos vértices?
- Si es así, ¿es una especie de NP completo? (Digo un poco porque técnicamente no es un problema de decisión ...)
- ¿Hay otros problemas en P que tienen versiones de conteo difíciles como esa también? **
Respuestas:
La clase de complejidad más común asociada a los problemas de conteo es #P . Decidir si hay una ruta simple desde un nodo dado a otro está claramente en NP. Contarlos está entonces en #P.
La respuesta a sus dos primeras dos preguntas es: sí, es difícil, es # P-completo (ref . ) .
El artículo de Wikipedia proporciona datos pertinentes: 1) los algoritmos probabilísticos son útiles para aproximar # P-funciones completas, y ese es el tipo de algoritmo utilizado para la aproximación en el artículo anterior. 2) Existen otros problemas fáciles con las versiones de conteo difíciles (# P-complete):
Ya sabe que si elimina la restricción "ruta simple", el problema cae en P (bueno, debe vincular la longitud de las rutas por un polinomio del tamaño del gráfico o dar el límite en unario)
fuente