Aproximación para contar el número de rutas simples

Aproximación para contar el número de rutas simples - en un gráfico general

Me han dicho que hay algunos buenos algoritmos de tiempo polinomiales para aproximar el número de rutas simples en un gráfico dirigido desde el vértice inicial dado hasta el vértice final dado . ¿Alguien sabe de una buena referencia sobre este tema? $s$ $t$

Antecedentes: contar el número exacto de rutas en un gráfico general es # P-completo, pero puede haber aproximaciones de tiempo polinomiales para el problema. Estoy especialmente interesado en aproximaciones aleatorias.

Gracias por adelantado.

ds.algorithms reference-request graph-algorithms approximation-algorithms counting-complexity bbejot
fuente

Tuve el mismo problema que resolver usando Random Walk.

@bbejot: Vea ¿Qué tan difícil es contar el número de rutas simples entre dos nodos en un gráfico dirigido? La única respuesta, de jmad, proporciona un enlace a un documento que proporciona una aproximación aleatoria

Carlos Linares López

Respuestas:

Este problema debería ser NP-hard reduciendo desde la longitud máxima de las rutas st.

La reducción simplemente reemplaza cada borde por, digamos, $k$ bordes paralelos. (Si no se siente cómodo con un gráfico múltiple, reemplace cada borde por una ruta de longitud 2.) El efecto de esto es que el número $C_{\ell}$ de rutas de longitud $\ell$ convierte en $k^\ell C_{\ell}$ . Por lo tanto, si $k$ es adecuadamente grande, el término correspondiente a las rutas más largas en el gráfico original dominará todo lo demás (incluso si $C_{\ell_{max}}=1$ ). Desde allí puede recuperar fácilmente la longitud del camino más largo.

Heng Guo
fuente