Se puede encontrar una camarilla 3 en un gráfico de -vértices G en el tiempo O ( n ω ) , donde ω < 2.376 es el exponente de multiplicación de la matriz, y en el espacio O ( n 2 ) por un resultado de Itai y Rodeh [1] . Básicamente, muestran que G contiene un triángulo si y solo si ( A ( G ) ) 3 tiene una entrada distinta de cero en su diagonal principal. Porque un triángulo también es un ciclo C 3nortesolO ( nω)ω < 2.376O ( n2)sol( A ( G ) )3C3, se pueden usar métodos generales de búsqueda de ciclos para detectar triángulos. Alon, Yuster y Zwick muestran cómo se pueden detectar triángulos en un gráfico de bordes en O ( m 2 ω / ( ω + 1 ) ) = O ( m 1.41 ) tiempo [6].metroO ( m2 ω / ( ω + 1 )) = O ( m1,41)
Durante mucho tiempo, el resultado de Nesetril y Poljak [2] fue el más conocido; mostraron que el número de camarillas de tamaño se puede encontrar en el tiempo O ( n ω k ) y O ( n 2 k ) espacio. Finalmente, Eisenbrand y Grandoni [3] mejoraron el resultado de Nesetril y Poljak para una camarilla ( 3 k + 1 ) y una camarilla ( 3 k + 2 ) para valores pequeños de k . Específicamente, dieron algoritmos para encontrar camarillas de tamaño 4, 5 y 7 en el tiempo O3 kO ( nω k)O ( n2 k)( 3 k + 1 )( 3 k + 2 )k , O ( n 4.220 ) y O ( n 5.714 ) , respectivamente.O ( n3.334)O ( n4.220)O ( n5.714)
kkkW[ 1 ]W[ 1 ]kk ≈ lognorte
solO ( n + m )kO ( n )
[1] Itai, Alon y Michael Rodeh. "Encontrar un circuito mínimo en un gráfico". SIAM Journal on Computing 7.4 (1978): 413-423.
[2] Nešetřil, Jaroslav y Svatopluk Poljak. "Sobre la complejidad del problema del subgrafo". Commentationes Mathematicae Universitatis Carolinae 26.2 (1985): 415-419.
[3] Eisenbrand, Friedrich y Fabrizio Grandoni. "Sobre la complejidad de la camarilla de parámetros fijos y el conjunto dominante". Informática teórica 326.1 (2004): 57-67.
[4] Downey, RG y Michael R. Fellows. "Fundamentos de la complejidad parametrizada". Textos no graduados en informática, Springer-Verlag (2012).
[5] Feige, Uriel y Kilian, Joe. "Sobre limitado no polinomial no determinismo". Chicago Journal of Theoretical Computer Science. (1997)
[6] Alon, Noga, Raphael Yuster y Uri Zwick. "Encontrar y contar ciclos de longitud dados". Algorithmica 17.3 (1997): 209-223.