La complejidad de contar rutas simples en un gráfico dirigido

16

Sea un dígrafo (no necesariamente un DAG) y sea s , t V ( G ) . ¿Cuál es la complejidad de contar el número de rutas s - t simples en G ? Gs,tV(G) stG

Esperaría que el problema sea # completo pero no he podido localizar una referencia exacta. P

También tenga en cuenta que varias preguntas similares se han respondido correctamente aquí y en otros lugares, pero no esta pregunta precisa: para enfatizar, no estoy interesado en contar caminatas y / o gráficos no dirigidos (en el primer caso, la variante está en y en el otro # P- duro).PPAG

SamiD
fuente
La completitud # P se aplica incluso para gráficos no dirigidos , y esto se discutió antes. Quizás una pregunta más interesante sería si se sabe que es -hard. APX
RB

Respuestas:

19

La prueba de integridad # P de contar sendas st simples en gráficos no dirigidos y dirigidos se puede encontrar en:

Leslie G. Valiant: la complejidad de los problemas de enumeración y confiabilidad . SIAM J. Comput. 8 (3): 410-421 (1979)

Del papel:

...
4. Algunos problemas de # P-complete
...
14. ST PATHS (es decir, CAMINOS DE EVITACIÓN AUTOMÁTICA) (dirigida o no dirigida)
Entrada: Salida: número de rutas (dirigidas) desde s hasta t que visitan cada nodo como máximo una vez. ...G;s,tV
st

Marzio De Biasi
fuente