Contando el número de rutas simples en un gráfico no dirigido

18

¿Cómo puedo determinar la cantidad de rutas simples únicas dentro de un gráfico no dirigido? Ya sea para una determinada longitud o para un rango de longitudes aceptables.

Recuerde que una ruta simple es una ruta sin ciclos, así que estoy hablando de contar el número de rutas sin ciclo.

Ryan
fuente
2
Esto ya se ha pedido en mathoverflow: mathoverflow.net/questions/18603/…
Listado el
55
En realidad, la pregunta en mathoverflow era encontrar todos los caminos y no contarlos. Encontrarlos puede ser mucho más difícil.
DCTLib
1
Además de las referencias que se dan en las respuestas, una observación trivial es que si uno puede contar el número de caminos de longitud entonces puede responder la pregunta de la existencia de un camino hamiltoniano. Lo más probable es que no sea P.n1
Saeed

Respuestas:

20

Hay varios algoritmos que cuentan las rutas simples de longitud en el tiempo f ( k ) n k / 2 + O ( 1 ) , que es mucho mejor que la fuerza bruta (tiempo O ( n k ) ). Ver, por ejemplo, Vassilevska y Williams, 2009 .kf(k)nk/2+O(1)O(nk)

Andreas Björklund
fuente
18

Es # P-completo (Valiant, 1979), por lo que es poco probable que lo haga mucho mejor que la fuerza bruta, si desea la respuesta exacta. Las aproximaciones son discutidas por Roberts y Kroese (2007).


B. Roberts y DP Kroese, " Estimación del número de rutas - t en un gráficost ". Journal of Graph Algorithms and Applications , 11 (1): 195-214, 2007.

LG Valiant, " La complejidad de los problemas de enumeración y confiabilidad ". SIAM Journal on Computing 8 (3): 410-421, 1979.

David Richerby
fuente
44
El documento de Roberts y Kroese no parece dar garantías de aproximación. ¿Hay un PTAS conocido por este problema?
Sasho Nikolov
3
@SashoNikolov, parece poco probable que haya un algoritmo de aproximación razonable. Dado obtenga G ' de G reemplazando cada nodo por una camarilla de tamaño N = n c donde n = | V | y c 1 . Para cada ruta simple de longitud en G hay aproximadamente ( N ! ) rutas en G ' . Entonces, si G tiene unG=(V,E)GGN=ncn=|V|c1G(N!)GG camino de Hamilton, habrá al menos ( N ! ) n o tan simple s - t caminos en G ' , y de otra manera a lo sumo algo como ( n - 1 ) ! ( N ! ) N - 1 sencilla s - t caminos. Por lo tanto, debería ser difícil aproximarlo en un factor de aproximadamente N ! / ( n - 1 ) ! » N c -st(N!)nstG(n1)!(N!)n1st. N!/(n1)!nc1!
Neal Young
6

Me gustaría agregar otro algoritmo de aproximación, uno parametrizado: para un fijo > 0 (o más precisamente, δ = Ω ( 1δ>0), puede calcularunaaproximación(1+δ)del número de rutas simples, en un gráfico dirigido o no dirigido, de longitudken el tiempoO(2O(k)).δ=Ω(1poly(k))(1+δ)kO(2O(k))

RB
fuente