¿Qué tan difícil es contar el número de caminos simples entre dos nodos de un grafo dirigido?

Question

Hay un algoritmo polinomial fácil decidir si existe un camino entre dos nodos de un grafo dirigido (acaba de hacer un recorrido gráfico de rutina con, por ejemplo, la profundidad de primera búsqueda).

Sin embargo, parece que, sorprendentemente, el problema se vuelve mucho más difícil si en lugar de las pruebas de la existencia queremos desea recuento el número de caminos.

Si permitimos caminos hacia los vértices de reutilización entonces no es una solución de programación dinámica para encontrar el número de caminos de s a t con n bordes. Sin embargo, si sólo permitimos caminos simples, que hacen vértices no reutilización, la única solución que se me ocurre es la fuerza bruta enumeración de los caminos , algo que no tiene tiempo de complejidad exponencial.

Así que les pido,

• está contando el número de caminos simples entre dos vértices duro?
• Si es así, es que tipo de NP-completo? (Digo especie de, ya que técnicamente no es un problema de decisión ...)
• ¿Hay otros problemas en P que tienen un conteo de versiones duras como eso también? **

Answer 1

La clase de complejidad común que más se asocia a problemas de conteo es #P . Decidir si hay un camino simple a partir de un nodo dado a otro es claramente en NP. Contándolos está entonces en #P.

Sobre el NP-completitud: incluso si eso no es un problema de decisión, sería casi no cabe en NP: puede haber $ n $ caminos, y no! determinismo no le ayuda en eso (que todavía había necesidad de comprobarlos todos)

La respuesta a las dos primeras dos preguntas es: sí, es difícil, es # P-completa (ref) .

La Wikipedia artículo da hechos pertinentes: 1) algoritmos de probabilidad son útiles para aproximar funciones # P-completo, y ese es el tipo de algoritmo utilizado para la aproximación en el artículo anterior. 2) Hay otros problemas fáciles con #-P completa versiones de conteo duros ():

• encontrar (lineal) vs. contando todas las asignaciones que satisfacen una fórmula DNF o una instancia de 2-SAT
• encontrar (lineal) de conteo vs topológica granulometrías
• encontrar (O (VE)) vs. contando coincidencia perfecta en grafos bipartitos

Usted ya sabe que si se quita la restricción "camino simple" el problema cae en P (así que tienes que limitan la longitud de los caminos por un polinomio del tamaño del gráfico o dar la atado en unario)