Haga clic en problema

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de noviembre de 2019; las comprobaciones requieren 4 ediciones .

El problema de la camarilla pertenece a la clase de problemas NP-completos en el campo de la teoría de grafos . Fue formulado por primera vez en 1972 por Richard Karp . [una]

Una camarilla en un gráfico no dirigido es un subconjunto de vértices, cada uno de los cuales está conectado por un borde del gráfico. En otras palabras, es un subgrafo completo del grafo original. El tamaño de la camarilla se define como el número de vértices en ella. El problema de la camarilla existe en dos versiones: en el problema de reconocimiento, se requiere determinar si hay unacamarilla de tamaño k en un grafo G dado , mientras que en una variante computacional, se requiere encontrar unacamarilla de tamaño máximo en una gráfica dada. dada la gráfica G.

NP-completo

El NP-completo del problema de la camarilla se deriva del NP-completo del problema del conjunto de vértices independientes . Es fácil mostrar que una condición necesaria y suficiente para la existencia de una camarilla de tamaño k es la presencia de un conjunto independiente de tamaño al menos k en el complemento del gráfico. Esto es obvio, ya que la completitud de un subgrafo significa que su complemento no contiene aristas.

Otra prueba de la completitud de NP se puede encontrar en Algorithms: Construction and Analysis. [2]

Algoritmos

En cuanto a otros problemas NP-completos, aún no se ha encontrado un algoritmo eficiente para encontrar una camarilla de un tamaño dado. Una búsqueda exhaustiva de todos los subgrafos posibles de tamaño k , comprobando si al menos uno de ellos está completo, es ineficiente, ya que el número total de dichos subgrafos en un grafo con v vértices es igual al coeficiente binomial ${v \elegir k} = \frac{v!}{k!(vk)!}.$

Otro algoritmo funciona así: dos camarillas de tamaño n y m se "pegan" en una camarilla grande de tamaño n + m , y se supone que un vértice separado del gráfico es una camarilla de tamaño 1 . El algoritmo termina tan pronto como no se pueden realizar más fusiones. El tiempo de ejecución de este algoritmo es lineal, pero es heurístico , ya que no siempre conduce a encontrar una camarilla del tamaño máximo. Un ejemplo de finalización fallida es el caso cuando los vértices pertenecientes a la camarilla máxima están separados y están en camarillas más pequeñas, y esta última ya no se puede “pegar” entre sí.

Se prueba que, bajo la condición de desigualdad de las clases P y NP , no existe un algoritmo de aproximación polinomial con error absoluto igual a arbitrario . Considere un gráfico u - el producto directo de un gráfico y una camarilla de tamaño . Obviamente, el número de clique del gráfico será igual a . Suponga que existe un algoritmo de aproximación con un error absoluto igual a . Luego alimentamos el gráfico como entrada y, bajo la condición, obtenemos . Sean camarillas de grafos de la forma , donde . Tenga en cuenta la validez de la desigualdad y sustitúyala en la desigualdad anterior de la siguiente manera: . Después de la transformación, obtenemos , lo que significa que existe tal que y, por lo tanto, el problema de la camarilla es solucionable en tiempo polinomial, lo que contradice la condición de desigualdad para las clases P y NP. $k\in {\matemáticas {N}}$ $GRAMO$ ${\displaystyle G^{k}=G\veces C_{k))$ $GRAMO$ $C_{k}$ $k$ ${\ Displaystyle G^{k}}$ $\omega (G^{k})=\omega (G)\cdot k$ $A$ $k\in {\matemáticas {N}}$ $A$ $G^{k+1}$ $OPT\leqslant A(I)+k$ $\omega (G^{k+1})-A(G^{k+1})=(k+1)\cdot \omega (G)-A(G^{k+1})\ leqslant k$ $C_{yo}$ ${\ Displaystyle G ^ {i}}$ $1\leqslant i\leqslant k+1$ ${\ Displaystyle C_ {i} \ leqslant \ omega (G)}$ $(k+1)\cdot \omega (G)-\sum _{i=1}^{k+1}|C_{i}|\leqslant k$ $\sum _{i=1}^{k+1}\omega (G)-|C_{i}|\leqslant k$ $i$ $C_{i}=\omega (G)$

Véase también

Algoritmo de Bron-Kerbosh : búsqueda rápida de todas las camarillas

Notas

↑ Karp, Richard (1972). “Reducibilidad entre problemas combinatorios” (PDF) . Actas de un simposio sobre la complejidad de los cálculos informáticos . Prensa Pleno. Archivado desde el original (PDF) el 29 de junio de 2011 . Consultado el 21 de marzo de 2010 . Parámetro obsoleto utilizado |deadlink=( ayuda )
↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmos: construcción y análisis = Introducción a los algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .

Literatura

Cook, Stephen A. (1971). “La complejidad de los procedimientos de demostración de teoremas” . Actas del Tercer Simposio Anual de ACM sobre Teoría de la Computación . Shaker Heights, Ohio. páginas. 151–158. Archivado desde el original el 3 de mayo de 2006 . Consultado el 11 de junio de 2007 . Parámetro obsoleto utilizado |deadlink=( ayuda ) Archivado el 3 de mayo de 2006 en Wayback Machine .
Garey, Michael R. & Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, ISBN 0-7167-1045-5 A1.2: GT19, pg.194.

Enlaces

Puntos de referencia desafiantes para la camarilla máxima, el conjunto independiente máximo, la cobertura mínima de vértices y la coloración de vértices

Problemas NP-completos
Problema de maximización del apilamiento (packing)	Envasado en contenedores embalaje bidimensional embalaje lineal embalaje por peso embalaje por valor El problema de la mochila
teoría de grafos teoría de conjuntos	Problema de cobertura de vértices Haga clic en problema El problema de un conjunto independiente (conjunto) Establecer problema de cobertura Problema de Steiner El problema del viajante de comercio Problema generalizado del viajante de comercio
Problemas algorítmicos	Problema de satisfacibilidad para fórmulas booleanas (en forma normal conjuntiva)
Juegos de lógica y rompecabezas.	Etiquetas generalizadas (juego en N 2 -1) problema de solución más corta Problemas cuyas soluciones se aplican en Tetris Problema de sudoku generalizado Problema de llenado de cuadrados latinos La tarea de Kakuro
Clases de dificultad La investigación de operaciones Mejoramiento optimización combinatoria Matemáticas Aplicadas Teoría de Algoritmos Programación dinámica 21 Problema de Karp NP-completo