- Problema de la clique
-
Problema de la clique
En complejidad computacional, el problema de la Clique o problema de la liga de amigos es un problema NP-completo según la Teoría de la complejidad computacional.
Una clique en un grafo es un conjunto de vértices dos a dos adyacentes. En el grafo de la derecha, los vértices 1, 2 y 5 forman una clique porque cada uno tiene un arco que le une a los otros. En cambio, los vértices 2, 3 y 4 no, dado que 2 y 4 no son adyacentes.
El problema de la clique es un problema de optimización para determinar cuándo un grafo contiene una clique de al menos un tamaño k. Una vez que tenemos k o más vertices que forman una clique, es trivial verificar que lo son, por eso es un problema NP. El correspondiente problema de optimización, consiste en encontrar una clique de tamaño máximo en un grafo (un subgrafo completo de tamaño máximo). Este problema se puede enunciar como un problema de decisión si la pregunta que se hace es saber si existe una clique de tamaño k en el grafo.
Algoritmos
Un ejemplo de algoritmo de fuerza bruta para encontrar una clique en un grafo consiste en listar todos los subconjuntos de vértices V y verificar para cada uno de ellos si forma una clique. Ese algoritmo es polinómico si k es una constante pero no lo es cuando se hace depender a k de, por ejemplo, |V|/2.
Un mejor algoritmo (Bron y Kerbosch) consiste en arrancar con cliques de un solo elemento (cualquier elemento sirve) e intentar mezclar cliques para obtener otras más grandes, hasta que no queden más mezclas por intentarse. Dos cliques pueden ser mezcladas si cada nodo de la primera es adyacente a cada nodo de la segunda.
Véase también
Categorías: Teoría de grafos | Problemas matemáticos | Problemas NP-completos | Optimización | Investigación Operativa
Wikimedia foundation. 2010.
