) algoritmo para el problema K-clique

15

El problema de la camarilla es un conocido completo donde el tamaño de la camarilla requerida es parte de la entrada. Sin embargo, el problema k-clique tiene un algoritmo de tiempo polinómico trivial ( cuando es constante). Estoy interesado en los límites superiores más conocidos cuando k es constante.nortePAGO(nortek)k

¿Existe un algoritmo con tiempo de ejecución ? Un algoritmo de tiempo también es aceptable. Además, ¿hay alguna consecuencia teórica de la complejidad para la existencia de tales algoritmos?O(nortek-1)o(nortek)

Mohammad Al-Turkistany
fuente

Respuestas:

20

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(norteω)ω<2.376O(norte2)sol(UN(sol))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(metro2ω/ /(ω+1))=O(metro1,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 O3kO(norteωk)O(norte2k)(3k+1)(3k+2)k , O ( n 4.220 ) y O ( n 5.714 ) , respectivamente.O(norte3.334)O(norte4.220)O(norte5.714)

kkkW[1]W[1]kkIniciar sesiónnorte

solO(norte+metro)kO(norte)


[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.

Juho
fuente