Algoritmos Computacionales
Tarea 2
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.
Problema
EL problema de clique es el siguiente:
Dado un grafo no dirigido G, y un número natural k, determinar si G posee un clique de tamaño k.
De nuevo:
Dado un grafo no dirigido cualquiera G= (V,E), en el cual V={1,2,…,n} es el conjunto
de los vértices del grafo y E es el conjunto de aristas. Un clique es un conjunto C de
vértices donde todo par de vértices de C esta conectado con una arista en G, es decir C
es un subgrafo completo.
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.
El correspondiente
problema de optimización, consiste en
encontrar una clique de tamaño máximo en un grafo.
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.
¿Qué es un clique?
El término proviene de la palabra inglesa clique, que define a un grupo de personas que comparten intereses en común.
En esta analogía, las personas serían los vértices y los intereses en común, las aristas. Cuando todas compartan un mismo interés, forman un grafo completo, es decir, forman un clique.
Un clique en un grafo no dirigido G es un conjunto de vértices V, tal que para todo par de vértices de V, existe una arista que las conecta, donde el
tamaño de un clique es el
número de vértices que contiene.
Ejemplo
El grafo G:
Tiene cliques {1,2,5} y {1,4,5} de tamaño 3.
Tiene cliques {2,3} y {3,4} de tamaño 2.
Aplicaciones al mundo real
Link Farm
Una granja de enlaces es un grupo de sitios web que enlazan a todos los sitios de un grupo entre sí. Esto es una forma de spamming para los indices de un motor de búsqueda.
Los motores de búsqueda necesitan una forma para encontrar la relevancia de una página. Un método para encontrarla es examinando todos los enlaces provenientes de páginas relevantes.
En otras palabras, crear una granja de enlaces tenía el propósito de incrementar la relevancia de un sitio web para aparecer en los primeros lugares de búsqueda. Para ello se creaban páginas que enlazaran unas a otras conteniendo los enlaces hacia aquellos sitios a los que se les deseaba dar popularidad.
Segmentación de imágenes y reconocimiento de patrones
Un problema muy común en computación gráfica es el de encontrar patrones dentro de una imagen. Hay una gran cantidad de problemas que entran dentro de esta categoría desde reconocimiento de bordes hasta búsqueda de figuras geométricas.
Un problema particular que se puede resolver utilizando una variación de Clique Máxima es la de reconocimiento de segmentos o regiones. Una región en una imagen es un conjunto de pixeles que comparten alguna característica.
Cálculo de probabilidades condicionales
El algoritmo general más común en redes bayesianas es el de agrupamiento "árbol cliques". El método de agrupamiento consiste en transformar la estructura de la red para obtener un árbol, mediante agrupación de nodos. Para ello, se hace una transformación de la red a un árbol de cliques máximas.
Biología
En el desarrollo evolutivo, una de las maneras de reconocer muchos de los procesos es mirar la expresión de genes en términos de las redes de la expresión de genes, que son los grafos. Los sistemas de regulación a menudo se revela como cliques en la red de expresión.
Al estudiar las estructuras de proteínas, una de las técnicas más importantes es analizar las proteínas similares, y encontrar cliques en común para las redes estructurales basados en grafos de las proteínas.
Algoritmos para resolver este problema
Algoritmo de fuerza bruta
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 como no lo es para este caso, tenemos un
exponencial de
n^k.
Algoritmo Bron-Kerbosch
Este algoritmo consiste en arrancar con cliques de un solo elemento 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.
Es eficiente en el peor de los casos por un resultado de Moon and Moser, donde un grafo de n vértices tiene a lo sumo 3^(n/3) cliques máximos, y el tiempo de ejecución del peor caso del algoritmo Bron-Kerbosch, con una estrategia dinámica que reduce al mínimo el número de llamadas recursivas realizadas en cada paso, es
O(3^(n/3)), que coincidan con este límite.
Para estos dos algoritmos es fácil saber cuál es mejor que el otro. Tenemos que:
- El mejor es Bron-Kerbosch.
- El peor es Fuerza bruta.
En el siguiente pdf encontramos la reducción SAT para el problema de clique:
Time reduction
Bibliografía:
Problema de Clique Máximo
Clasificación de problemas
Clique problem - Wikipedia
Problema de la clique - Wikipedia
Complejidad computacional
Cliques and a bit of biology
