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 ?
Esperaría que el problema sea # completo pero no he podido localizar una referencia exacta.
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).
Respuestas:
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:
...G;s,t∈V
s t
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. ...
fuente