Problema do clique

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em ciência da computação, o problema clique refere-se a qualquer problema que possui como objetivo encontrar sub-grafos 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 gráfo 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[editar | editar código-fonte]

Embora sub-grafos 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[editar | editar código-fonte]

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 todos 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 freqüentemente, 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 booleano: 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[editar | editar código-fonte]

Maximal versus Máximo[editar | editar código-fonte]

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[editar | editar código-fonte]

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 Chiba & Nishizeki (1985) 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 arboracidade 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 Itai & Rodeh (1978) 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 Alon, Yuster & Zwick (1994) 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[editar | editar código-fonte]

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 Bron & Kerbosch (1973) 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 Tsukiyama et al. (1977) 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; Chiba & Nishizeki (1985) melhorou esse tempo para O(ma) por clique, onde a é a arboricidade do dado grafo. Makino & Uno (2004) 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.

Achando cliques máximos em grafos arbitrários[editar | editar código-fonte]

É possível achar o clique máximo, ou o número do clique, de um grafo arbitrário com n vértices em tempo O(3n/3) = O(1.4422n) usando um dos algoritmos descritos acima para listar todos os cliques maximais e retornar o maior deles. Contudo, para essa variante do problema do clique, melhores algoritmos de pior caso são possíveis. O algoritmo de Tarjan & Trojanowski (1977) resolve o problema em tempo O(2n/3) = O(1.2599n); É um esquema recursivo com backtracking similar ao do algoritmo de Bron–Kerbosch, mas é capaz de eliminar algumas chamadas recursivas quando pode ser mostrado que algumas outras combinações de vértices não usados na chamada é garantia para levar a um solução pelo menos tão boa quanto a atual. Jian (1986) melhorou esse tempo O(20.304n) = O(1.2346n). Robson (1986) melhorou o anterior para o tempo O(20.276n) = O(1.2108n) ao custo de maior uso de espaço, com um esquema similar de backtracking com uma análise de caso mais complicada, junto com uma técnica de programação dinâmica na qual a solução ótima é pré computada para todos os pequenos subgrafos conectados do grafo complementar e essas soluções parciais são usadas como um atalho na recursão do backtracking. O algoritmo mais rápido conhecido atualmente é o de Robson (2001) que roda em tempo O(20.249n) = O(1.1888n).

Também houve pesquisa extensiva em algoritmos heurísticos para resolver problemas de clique máximo sem a garantia de runtime em pior caso, baseado em métodos incluindo branch and bound, busca local, algoritmos gulosos e constraint programing. Metodologias incomuns de computação para achar cliques incluem computação em DNA e computação quântica adiabática. O problema do máximo clique foi assunto de um desafio de implementação patrocinado pelo DIMACS em 1992-1993, e uma coleção de grafos usados como benchmarks para o desafio está disponível publicamente.

Casos especiais de grafos[editar | editar código-fonte]

Grafos planares e outras famílias de grafos esparsos , foram discutidas acima: eles tem muitos cliques maximais, de tamanho limitado, que podem ser listados em tempo linear. Em particular, para grafos planares, qualquer clique pode ter no máximo 4 vértices, pelo teorema de Kuratowski's.

Grafos perfeitos são definidos pelas propriedades que o seu número de clique é igual ao seu número cromático, e que isso permanece verdade em cada um dos seus subgrafos induzidos. Para grafos perfeitos, é possível achar o clique máximo em tempo polinomial, usando um algoritmo baseado em Semidefinite programming. Contudo, esse método é complexo e não combinatório e algoritmos especializados em achar o clique foram desenvolvidos para muitas subclasses de grafos perfeitos. No complemento de grafos bipartidos, o teorema de König's permite que o problema de clique máximo seja resolvido usando técnicas para matching. Em outra classe de grafos perfeitos, os grafos de permutação, o clique máximo é a mais longa sub seqüência decrescente da permutação definindo o grafo e pode ser achada usando algoritmos conhecidos para esse problema. Em grafos cordais, os clique maximais são um subconjunto de um dos n cliques formados como parte de uma de ordem de eliminação.

Em alguns casos, esses algoritmos podem ser estendidos para outras, não perfeitas, classes de grafos: por exemplo, em um grafo circular, os vizinhos de cada vertice é um grafo de permutação, então o clique Maximo encontrado em um grafo circular pode ser achado usando o algoritmo para grafos de permutação para cada vizinho. Similarmente, em um unit disk graph(com uma representação geométrica conhecida), existe um algoritmo em tempo polinomial para cliques maximos baseado no algoritmo usado para o complemento de grafos bi partidos.

O problema algoritmo de achar o clique Maximo em um grafo aleatório desenhado a partir do modelo de Erdos–Rényi(no qual cada aresta aparece com uma probabilidade de ½ independente das outras) foi sugerido Karp (1976). Apesar do número de clique de tais grafos ser muito próximo de 2 log2n, tanto algoritmos gulosos mais simples quanto técnicas sofisticadas de aproximações aleatórias só acham cliques com tamanho log2n, e o número de cliques maximais em tais grafos tem alta probabilidade de ser exponenciais em log2n prevenindo que exista um solução em tempo polinomial que liste todos eles. Por causa da dificuldade desse problema, muitos autores têm investigado variantes do problema na qual o grafo aleatório é modificado adicionando um grande clique, de tamanho proporcional a √n. É possível achar esse clique escondido com grande probabilidade em tempo polinomial, ou usando spectral methods ou semidefinite programing.

Algoritmos de Aproximação[editar | editar código-fonte]

Muitos autores têm considerado algoritmos de aproximação que tentam achar um clique ou um conjunto independente que, apesar de não ser o máximo, tem um tamanho o mais perto possível do máximo que pode ser encontrado em tempo polinomial. Apesar de que boa parte desse trabalho seja focado em conjuntos independentes em grafos esparsos, um caso que não faz sentido para o problema do clique complementar, também houve trabalho em algoritmos de aproximação que não usam a suposição de grafos esparços. Feige (2004) descreve um algoritmo de tempo polinomial que acha um clique de tamanho Ω((log n/log log n)2) em qualquer grafo que tenho um número de clique Ω(n/logkn) para qualquer constante k. Combinando esse algoritmo para achar cliques em grafos com números de clique entre n/log n e n/log3n com um algoritmo diferente de Boppana & Halldórsson (1992) para achar cliques em grafos com número de clique maior, e escolhendo um clique de 2 vertices caso ambos os algoritmos falhem, Feige prove um algoritmo de aproximação que acha o clique com um número de vertices dentro de um fator de O(n(log log n)2/log3n) do maximo.

Limites inferiores[editar | editar código-fonte]

NP-completude[editar | editar código-fonte]

O problema de decisão do clique é NP-completo. Foi um dos 21 problemas originais de Richard Karp’s mostrados no seu trabalho de 1972 “Reducibility Among Combinatorial Problems". Esse problema também foi mencionado no trabalho de Stephen Cook's introduzindo a teoria de problemas NP-completos. O problema de achar um clique máximo é NP-difícil: Se o mesmo for resolvido, também é possível resolver o problema da decisão, comparando o tamanho do clique máximo com o tamanho do parâmetro dado com entrada do problema da decisão. A prova da NP-completude de Karp é uma redução do problema SAT para formulas na forma normal conjuntiva, o qual for provado NP-completo no teorema de Cook-levin. Dado uma formula na fnc, karp forma um grafo que tem um vertice para cada par(v,c), onde v é uma varivavel ou a sua negação e c é a clausula da formula que contem v. Vértices são conectados por uma aresta se eles representam associação compatível para diferente clausulas: isto é, existe uma aresta entre (v, c) para (u, d) se c ≠ d e u e v não são suas respectivas negações. Se k denota o número de clausulas na formula fnc, então k-vertices cliques nesse grafo representam maneiras de associar valores verdade para algumas de suas variáveis a fim de satisfazer sua formula; Portanto, a formula é satisfatível se e somente se existe um clique de k vertices. Alguns problemas NP-completo(como o do caixeiro viajante em grafos planares) podem ser resolvidos em tempo que é exponencial em uma função sub-linear do tamanho do paramentro n. Porém, como Impagliazzo, Paturi & Zane (2001) descreve, é improvável que tais limites existam para o problema do clique em grafos arbitrários, pois isso implicaria em limites subexponenciais similares para muitos outros problems NP-Completos.

Referencias[editar | editar código-fonte]