Em ciência da computação, o problema do clique refere-se a qualquer problema que possui como objetivo encontrar subgrafos completos ("cliques") em um grafo. Como exemplo, o problema de encontrar conjuntos de nós em que todos os elementos estão conectados entre si.
Por exemplo, o problema clique surge no cenário seguinte. Considere uma rede social, onde os vértices do grafo representam pessoas, e as arestas representam o conhecimento mútuo. Para encontrar um maior subconjunto de pessoas, em que todas conhecem umas as outras, pode-se sistematicamente inspecionar todos os subconjuntos, um processo que é muito demorado para ser prático para as redes sociais, mesmo que pequenas. Embora a pesquisa por força bruta possa ser melhorada através de algoritmos mais eficientes, todos estes algoritmos levam tempo exponencial para resolver o problema. Portanto, grande parte da teoria sobre o problema do clique é dedicado à identificação de tipos especiais de gráfo que admitem algoritmos mais eficientes, ou a definição da dificuldade computacional do problema geral em vários modelos de computação. Junto com seus aplicativos em redes sociais , o clique também tem muitas aplicações em bioinformática e química computacional.
Problemas que envolvem o clique:
encontrar o clique máximo (um clique com o maior número de vértices); encontrar o clique com maior valor em um grafo valorado; listar todos os cliques máximos (cliques que não podem ser ampliados); resolver o problema de decisão de testar se um grafo contém um clique maior que um tamanho determinado.
Esses problemas são todos difíceis: o problema de decisão clique é NP-completo (um dos 21 problemas NP-Completo de Karp), e listar todos os cliques máximos pode exigir tempo exponencial. No entanto, existem algoritmos para esses problemas que são executados em tempo exponencial ou que lidam com grafos de entrada mais especializados em tempo polinomial.
História Embora subgrafos completos tenham sido estudados por mais tempo na matemática, o termo "clique" e o problema da listagem de cliques algoritmicamente vêm das ciências sociais, onde subgrafos completos são usados para modelar cliques sociais, grupos de pessoas que se conhecem. O termo "clique" vem de Luce & Perry (1949), e o primeiro algoritmo para resolver o problema clique foi demonstrado por Harary & Ross (1957), motivados pela aplicação sociológica.
Desde o trabalho de Harary e Ross, muitos outros criaram algoritmos para várias versões do problema clique. Na década de 1970, os pesquisadores começaram a estudar estes algoritmos do ponto de vista da análise de pior caso, ver, por exemplo, Tarjan & Trojanowski (1977), um trabalho inicial sobre a complexidade do pior caso do problema do clique máximo. Também na década de 1970, começando com o trabalho de Cook (1971) e Karp (1972), os pesquisadores começaram a encontrar justificativa matemática para a dificuldade percebida do problema clique na teoria da NP-completude e resultados relacionados com intratabilidade. Na década de 1990, uma série inovadora de artigos começando por Feige et al. (1991) e relatado na época nos principais jornais, mostrou que não é sequer possível aproximar o problema com precisão e eficiência.
Definição Um grafo não-direcionado é formado por um conjunto finito de vértices e um conjunto de pares não ordenados de vértices, que são chamados de arestas. Por convenção, na análise de algoritmos, o número de vértices do grafo é denotado por n e o número de arestas é denotado por m. Um clique em um grafo G é um subgrafo completo de G, ou seja, é um subconjunto S de vértices tal que todo par de nós está conectado por uma aresta. Uma clique maximal é um clique para o qual não se pode mais adicionar vértices; um clique máximo é um clique que inclui o maior número possível de vértices em um grafo.
Vários problemas relacionados à busca de cliques em grafos já foram estudados:
No problema do clique máximo, a entrada é um grafo não direcionado, e a saída é uma clique máximo no grafo. Se houver vários cliques máximos, apenas um precisa ser a saída. No problema do clique máximo com pesos, a entrada é um grafo não direcionado, com pesos em seus vértices (ou, menos frequentemente, arestas) e a saída é clique com peso total máximo. O problema do clique máximo é o caso especial em que todos os pesos são um. No problema k-clique, a entrada é um grafo não direcionado e um número k, e a saída é um clique de tamanho k, se existir um (ou, às vezes, todos os cliques de tamanho k). No problema de decisão de clique, a entrada é um grafo não direcionado e um número k, e a saída é um valor booliano: verdadeiro se o grafo contém um k-clique, e falso caso contrário.
Os três primeiros destes problemas são todos importantes em aplicações práticas. Já o problema de decisão do clique é necessário para aplicar a teoria da NP-completude aos problemas de encontrar cliques em grafos. O problema do clique e o problema dos conjuntos independentes são complementares: um clique em G é um conjunto independente no grafo complementar de G e vice versa. Portanto, muitos resultados computacionais podem ser aplicados igualmente para ambos os problemas e algumas pesquisas não distinguem claramente a diferença entre esses dois problemas. Contudo, os dois problemas têm diferentes propriedades quando aplicados a famílias restritas de grafos; por exemplo, o problema do clique pode ser resolvido em tempo polinomial para grafos planares enquanto o problema de conjuntos independentes continua NP-difícil.
Algoritmos
Maximal versus Máximo Um clique maximal, às vezes chamado de inclusão-maximal, é um clique que não é incluso em um clique maior. Encontrar um clique maximal é trivial: Começando do primeiro vértice, expanda o clique atual iterando sobre os vértices restantes do grafo, adicionar um vértice se ele está conectado a todos os outros vértices do clique atual. Esse algoritmo roda em tempo O(m). Contudo, cliques maximais podem ser muito pequenos; Um grafo pode conter um clique de tamanho n−1, mas um clique maximal de tamanho 2. Então, enquanto um máximo (ex., o maior) clique é necessariamente maximal, o inverso não se mantém, e a maior atenção dos algoritmos é dada ao problema muito mais difícil de achar um máximo.
Cliques de tamanho fixo Um algoritmo de força bruta para testar se um grafo G contém um k-vertices clique, e achar qualquer clique que ele contém, é examinar cada subgrafo com pelo menos k verticies e checar se ele forma um clique. Esse algoritmo toma o tempo O(nk k2): existem O(nk) subgrafos para checar, cada um dos quais tem O(k2) arestas cuja presença em G precisa ser checada. Portanto, o problema pode ser resolvido em tempo polinomial quando k é uma constante fixa. Mas quando k é uma entrada para o problema o tempo é exponencial. O caso não-trivial mais simples de problemas relacionados a achar o clique é achar um triangulo em um grafo, ou de forma análoga, determinar se o grafo não contém nenhum triangulo. Em um grafo com m arestas, podem existir no máximo Θ(m3/2) triângulos; O pior caso ocorre quando G é um clique. Portanto, algoritmos para listar todos os triângulos devem tomar pelo menos o tempo Ω(m3/2) no pior caso, e são conhecidos algoritmos que seguem esse limite. Por exemplo descrevem um algoritmo que ordena os vértices na ordem do maior grau pro menor e então itera sobre cada vértice v na lista ordenada, procurando por triângulos que incluem v e não incluem nenhum vértice numa posição anterior da lista. Para fazê-lo o algoritmo marca todos os vizinhos de v, procura por todas as arestas incidentes a um vizinho de v retornando um triangulo para cada aresta que tem 2 pontos finais marcados, e então remove as marcas e deleta v do grafo. Como os autores mostram, o tempo para o algoritmo é proporcional a arboricidade do grafo(a(G)) vezes o número de arestas, que é O(m a(G)). Já que a arboricidade é no máximo O(m1/2), esse algoritmo roda em tempo O(m3/2). Generalizando, todos os k-vertices cliques pode ser listados por um algoritmo similar que toma tempo proporcional ao número de arestas vezes (k-2) ézima potencia da arboricidade. Para grafos de arboricidade constante, como grafos planares, esse algoritmo toma tempo O(m).
Se o objetivo é achar um único triangulo, ou a garantia que o grafo não possui nenhum, algoritmos mais rápidos são possíveis. Como observou, o grafo contem um triangulo se e somente se a sua matriz de adjacência e o quadrado da matriz de adjacência contem uma quantidade diferentes de 0 de entradas na mesma célula; Portanto, técnicas rápidas de multiplicação de matrizes como o algoritmo de Coppersmith–Winograd podem ser aplicadas para achar triângulos em tempo O(n2.376), o que pode ser mais rápido que O(m3/2) para grafos suficientemente densos melhorou o algoritmo de achar triângulos O(m3/2) para O(m1.41) usando rápida multiplicação de matrizes. Essa ideia do uso de rápida multiplicação de matrizes para achar triângulos também foi estendida para problemas de achar k-cliques com valores maiores para k.
Listando todos os cliques maximais Como um resultado de Moon & Moser (1965), qualquer n-vertice grafo tem no máximo 3n/3 cliques maximais. O algoritmo de Bron–Kerbosch é um procedimento recursivo com backtracking de que modifica um clique candidato considerando um vértice por vez, ou adicionando ele ao clique candidato ou a um conjunto de vértices excluídos que não podem estar no clique, mas devem ter algum não-vizinho no eventual clique; variantes desse algoritmo tem o pior caso em tempo O(3n/3). Portanto isso prove uma solução de pior caso ótima para o problema de achar todos os conjuntos maximais independentes; O algoritmo de Bron–Kerbosch foi amplamente reportado como sendo mais rápido na pratica que suas alternativas. Como mostrou, também é possível listar todos os cliques maximais em um grafo em um tempo que é polinomial por clique gerado. Um algoritmo como o dele na qual o tempo depende no tamanho da saída é conhecido como algoritmo sensível a saída. O algoritmo deles é baseado nas duas seguintes observações, relacionando os cliques maximais do dado grafo G a os cliques maximais de um grafo G/ v formado pela remoção de um vértice arbitrário v de G: Para cada clique maximal C de G/v, ou C continua para formar um clique maximal em G, ou C u {v} forma um clique maximal em G. Portanto, G tem pelo menos tantos cliques maximais quanto G/v. Cada clique maximal em G que não contém v é um clique maximal em G/v, e cada clique maximal em G que contém v pode ser formado por um clique maximal C em G/v adicionando v e removendo os não-vizinhos de v que pertencem a C. Usando essas observações eles podem gerar todos cliques maximais em G gerando um algoritmo recursivo que, para cada clique maximal C em G/v, retorna C e o clique formado pela adição de v a C e removendo os não-vizinhos de v. Contudo, alguns cliques de G podem ser gerados dessa maneira a partir de mais de um clique parente de G/v, então eles eliminam os repetidos retornando um clique somente se o seu parente em G/v é lexicograficamente Maximo dentre todos os cliques parentes possíveis. Na base desse princípio, eles mostraram que todos os cliques maximais em G podem ser gerados em temp O(mn) por clique, onde m é o número de arestas em g e n é o número de vértices; melhorou esse tempo para O(ma) por clique, onde a é a arboricidade do dado grafo. prove uma alternativa para o algoritmo sensível a saída baseado em multiplicação rápida de matrizes, e and Johnson & Yannakakis (1988) mostrou que é possível listar todos os cliques maximais em ordem lexicográfica com delay polinomial por clique, apesar do inverso dessa ordem ser NP-hard para gerar. Na base desse resultado, é possível listar todos os cliques maximais em tempo polinomial, para famílias de grafos das quais o número de cliques é limitado polinomialmente. Essas famílias incluem grafos completos, grafos livres de triângulos, grafos de intervalo e grafos planares.