Problema do clique

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.