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.

História[editar | editar código-fonte]

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[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 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[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(n^k k²): existem O(n^k) subgrafos para checar, cada um dos quais tem O(k²) 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 Θ(m^3/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 Ω(m^3/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(m^1/2), esse algoritmo roda em tempo O(m^3/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 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(n^2.376), o que pode ser mais rápido que O(m^3/2) para grafos suficientemente densos Alon, Yuster & Zwick (1994) melhorou o algoritmo de achar triângulos O(m^3/2) para O(m^1.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 3^n/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(3^n/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(3^n/3) = O(1.4422ⁿ) 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(2^n/3) = O(1.2599ⁿ); É 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(2^0.304n) = O(1.2346ⁿ). Robson (1986) melhorou o anterior para o tempo O(2^0.276n) = O(1.2108ⁿ) 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(2^0.249n) = O(1.1888ⁿ).

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 sequê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 vértice é 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 máximos 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 log₂n, tanto algoritmos gulosos mais simples quanto técnicas sofisticadas de aproximações aleatórias só acham cliques com tamanho log₂n, e o número de cliques maximais em tais grafos tem alta probabilidade de ser exponenciais em log²n 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 esparsos. Feige (2004) descreve um algoritmo de tempo polinomial que acha um clique de tamanho Ω((log n/log log n)²) em qualquer grafo que tenho um número de clique Ω(n/log^kn) para qualquer constante k. Combinando esse algoritmo para achar cliques em grafos com números de clique entre n/log n e n/log³n 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)²/log³n) do máximo.

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 vértice para cada par(v,c), onde v é uma variável 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 é satisfazível se e somente se existe um clique de k vértices.

Alguns problemas NP-completo(como o do caixeiro viajante em grafos planares) podem ser resolvidos em tempo que é exponencial em uma função sublinear do tamanho do parâmetro 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 problemas NP-Completos.

Referencias[editar | editar código-fonte]

Abello, J.; Pardalos, P. M.; Resende, M. G. C. (1999), Abello, J.; Vitter, J., eds., «External Memory Algorithms», ISBN 0821811843, American Mathematical Society, On maximum clique problems in very large graphs, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 50, pp. 119–130 .
Alon, N.; Boppana, R. (1987), «The monotone circuit complexity of boolean functions», Combinatorica, 7 (1): 1–22, doi:10.1007/BF02579196 .
Alon, N.; Krivelevich, M.; Sudakov, B. (1998), «Finding a large hidden clique in a random graph», Random Structures & Algorithms, 13 (3–4): 457–466, doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W .
Alon, N.; Yuster, R.; Zwick, U. (1994), «Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands», Finding and counting given length cycles, pp. 354–364 .
Amano, K.; Maruoka, A. (1998), «Proc. Symp. Mathematical Foundations of Computer Science», Springer-Verlag, A superpolynomial lower bound for a circuit computing the clique function with at most (1/6)log log n negation gates, Lecture Notes in Computer Science, 1450, pp. 399–408 ^{[ligação inativa]}.
Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), «Proof verification and the hardness of approximation problems», Journal of the ACM, 45 (3): 501–555, doi:10.1145/278298.278306, Predefinição:ECCC . Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267823.
Arora, S.; Safra, S. (1998), «Probabilistic checking of proofs: A new characterization of NP», Journal of the ACM, 45 (1): 70–122, doi:10.1145/273865.273901 . Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267824.
Balas, E.; Yu, C. S. (1986), «Finding a maximum clique in an arbitrary graph», SIAM Journal on Computing, 15 (4): 1054–1068, doi:10.1137/0215075 .
Battiti, R.; Protasi, M. (2001), «Reactive local search for the maximum clique problem», Algorithmica, 29 (4): 610–637, doi:10.1007/s004530010074 .
Bollobás, Béla (1976), «Complete subgraphs are elusive», Journal of Combinatorial Theory, Series B, ISSN 0095-8956, 21 (1): 1–7, doi:10.1016/0095-8956(76)90021-6 .
Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M. (1999), «Handbook of Combinatorial Optimization», Kluwer Academic Publishers, The maximum clique problem, 4, pp. 1–74 .
Boppana, R.; Halldórsson, M. M. (1992), «Approximating maximum independent sets by excluding subgraphs», BIT, 32 (2): 180–196, doi:10.1007/BF01994876 .
Bron, C.; Kerbosch, J. (1973), «Algorithm 457: finding all cliques of an undirected graph», Communications of the ACM, 16 (9): 575–577, doi:10.1145/362342.362367 .
Carraghan, R.; Pardalos, P. M. (1990), «Cópia arquivada» (PDF), Operations Research Letters, 9 (6): 375–382, doi:10.1016/0167-6377(90)90057-C, consultado em 12 de dezembro de 2011, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 .
Cazals, F.; Karande, C. (2008), «A note on the problem of reporting maximal cliques» (PDF), Theoretical Computer Science, 407 (1): 564–568, doi:10.1016/j.tcs.2008.05.010 .
Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), «Strong computational lower bounds via parameterized complexity», J. Comput. Syst. Sci., 72 (8): 1346–1367, doi:10.1016/j.jcss.2006.04.007
Chiba, N.; Nishizeki, T. (1985), «Arboricity and subgraph listing algorithms», SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017 .
Childs, A. M.; Farhi, E.; Goldstone, J.; Gutmann, S. (2002), «Finding cliques by quantum adiabatic evolution», Quantum Information and Computation, 2 (3): 181–191, arXiv:quant-ph/0012104 .
Childs, A. M.; Eisenberg, J. M. (2005), «Quantum algorithms for subset finding», Quantum Information and computation, 5 (7): 593–604, arXiv:quant-ph/0311038 .
Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. (1990), «Unit disk graphs», Discrete Mathematics, 86 (1–3): 165–177, doi:10.1016/0012-365X(90)90358-O
Cook, S. A. (1971), «Proc. 3rd ACM Symposium on Theory of Computing» 🔗, The complexity of theorem-proving procedures, pp. 151–158, doi:10.1145/800157.805047 |capítulo= ignorado (ajuda).
Downey, R. G.; Fellows, M. R. (1995), «Fixed-parameter tractability and completeness. II. On completeness for W[1]», Theoretical Computer Science, 141 (1–2): 109–131, doi:10.1016/0304-3975(94)00097-3 .
Downey, R. G.; Fellows, M. R. (1999), Parameterized complexity, ISBN 0-387-94883-X, Springer-Verlag .
Eisenbrand, F.; Grandoni, F. (2004), «On the complexity of fixed parameter clique and dominating set», Theoretical Computer Science, 326 (1–3): 57–67, doi:10.1016/j.tcs.2004.05.009 .
Eppstein, David; Löffler, Maarten; Strash, Darren (2010), Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo, eds., «21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea», ISBN 978-3-642-17516-9, Springer-Verlag, Listing all maximal cliques in sparse graphs in near-optimal time, Lecture Notes in Computer Science, 6506, pp. 403–414, arXiv:1006.5440, doi:10.1007/978-3-642-17517-6_36 |capítulo= ignorado (ajuda).
Eppstein, David; Strash, Darren (2011), «10th International Symposium on Experimental Algorithms», Listing all maximal cliques in large sparse real-world graphs, arXiv:1103.0318 .
Erdős, Paul; Szekeres, George (1935), «A combinatorial problem in geometry» (PDF), Compositio Mathematica, 2: 463–470 .
Even, S.; Pnueli, A.; Lempel, A. (1972), «Permutation graphs and transitive graphs», Journal of the ACM, 19 (3): 400–410, doi:10.1145/321707.321710 .
Fahle, T. (2002), «Proc. 10th European Symposium on Algorithms», ISBN 978-3-540-44180-9, Springer-Verlag, Simple and fast: Improving a branch-and-bound algorithm for maximum clique, Lecture Notes in Computer Science, 2461, pp. 47–86, doi:10.1007/3-540-45749-6_44 |capítulo= ignorado (ajuda).
Feige, U. (2004), «Approximating maximum clique by removing subgraphs», SIAM Journal on Discrete Mathematics, 18 (2): 219–225, doi:10.1137/S089548010240415X .
Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), «Proc. 32nd IEEE Symp. on Foundations of Computer Science», ISBN 0-8186-2445-0, Approximating clique is almost NP-complete, pp. 2–12, doi:10.1109/SFCS.1991.185341 |capítulo= ignorado (ajuda).
Feige, U.; Krauthgamer, R. (2000), «Finding and certifying a large hidden clique in a semirandom graph», Random Structures and Algorithms, 16 (2): 195–208, doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A .
Garey, M. R.; Johnson, D. S. (1978), «"Strong" NP-completeness results: motivation, examples and implications», Journal of the ACM, 25 (3): 499–508, doi:10.1145/322077.322090 .
Gavril, F. (1973), «Algorithms for a maximum clique and a maximum independent set of a circle graph», Networks, 3 (3): 261–273, doi:10.1002/net.3230030305 .
Goldmann, M.; Håstad, J. (1992), «A simple lower bound for monotone clique using a communication game», Information Processing Letters, 41 (4): 221–226, doi:10.1016/0020-0190(92)90184-W .
Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, ISBN 0444515305, Computer Science and Applied Mathematics, Academic Press .
Gröger, Hans Dietmar (1992), «On the randomized complexity of monotone graph properties» (PDF), Acta Cybernetica, 10 (3): 119–127, consultado em 2 de outubro de 2009
Grosso, A.; Locatelli, M.; Della Croce, F. (2004), «Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem», Journal of Heuristics, 10 (2): 135–152, doi:10.1023/B:HEUR.0000026264.51747.7f .
Grötschel, M.; Lovász, L.; Schrijver, A. (1988), «Geometric Algorithms and Combinatorial Optimization», ISBN 038713624X, Springer–Verlag, 9.4 Coloring Perfect Graphs, Algorithms and Combinatorics, 2, pp. 296–298 .
Gutin, G. (2004), Gross, J. L.; Yellin, J., eds., «Handbook of graph theory», ISBN 9781584880905, CRC Press, 5.3 Independent sets and cliques, Discrete Mathematics & Its Applications, pp. 389–402 .
Halldórsson, M. M. (2000), «Approximations of Weighted Independent Set and Hereditary Subset Problems» (PDF), Journal of Graph Algorithms and Applications, 4 (1): 1–16 .
Harary, F.; Ross, I. C. (1957), «A procedure for clique detection using the group matrix», American Sociological Association, Sociometry, 20 (3): 205–215, JSTOR 2785673, MR 0110590, doi:10.2307/2785673 .
Håstad, J. (1999), «Clique is hard to approximate within n^1 − ε», Acta Mathematica, 182 (1): 105–142, doi:10.1007/BF02392825 .
Impagliazzo, R.; Paturi, R.; Zane, F. (2001), «Which problems have strongly exponential complexity?», Journal of Computer and System Sciences, 63 (4): 512–530, doi:10.1006/jcss.2001.1774 .
Itai, A.; Rodeh, M. (1978), «Finding a minimum circuit in a graph», SIAM Journal on Computing, 7 (4): 413–423, doi:10.1137/0207033 .
Jerrum, M. (1992), «Large cliques elude the Metropolis process», Random Structures and Algorithms, 3 (4): 347–359, doi:10.1002/rsa.3240030402 .
Jian, T (1986), «An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem», IEEE Computer Society, IEEE Transactions on Computers, ISSN 0018-9340, 35 (9): 847–851, doi:10.1109/TC.1986.1676847 .
Johnson, D. S.; Trick, M. A., eds. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993, ISBN 0821866095, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, American Mathematical Society .
Johnson, D. S.; Yannakakis, M. (1988), «On generating all maximal independent sets», Information Processing Letters, 27 (3): 119–123, doi:10.1016/0020-0190(88)90065-8 .
Karp, Richard M. (1972), Miller, R. E.; Thatcher, J. W., eds., «Complexity of Computer Computations» (PDF), New York: Plenum, Reducibility among combinatorial problems, pp. 85–103 .
Karp, Richard M. (1976), Traub, J. F., ed., «Algorithms and Complexity: New Directions and Recent Results», New York: Academic Press, Probabilistic analysis of some combinatorial search problems, pp. 1–19 .
Katayama, K.; Hamamoto, A.; Narihisa, H. (2005), «An effective local search for the maximum clique problem», Information Processing Letters, 95 (5): 503–511, doi:10.1016/j.ipl.2005.05.010 .
Khot, S. (2001), «Proc. 42nd IEEE Symp. Foundations of Computer Science», ISBN 0-7695-1116-3, Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring, pp. 600–609, doi:10.1109/SFCS.2001.959936 |capítulo= ignorado (ajuda).
Kloks, T.; Kratsch, D.; Müller, H. (2000), «Finding and counting small induced subgraphs efficiently», Information Processing Letters, 74 (3–4): 115–121, doi:10.1016/S0020-0190(00)00047-8 .
Lipton, R. J.; Tarjan, R. E. (1980), «Applications of a planar separator theorem», SIAM Journal on Computing, 9 (3): 615–627, doi:10.1137/0209046 .
Luce, R. Duncan; Perry, Albert D. (1949), «A method of matrix analysis of group structure», Psychometrika, 14 (2): 95–116, PMID 18152948, doi:10.1007/BF02289146 .
Magniez, Frederic; Santha, Miklos; Szegedy, Mario (2003). «Quantum Algorithms for the Triangle Problem». arXiv:quant-ph/0310134 .
Makino, K.; Uno, T. (2004), «Algorithm Theory: SWAT 2004», Springer-Verlag, New algorithms for enumerating all maximal cliques, Lecture Notes in Computer Science, 3111, pp. 260–272 .
Moon, J. W.; Moser, L. (1965), «On cliques in graphs», Israel Journal of Mathematics, 3: 23–28, MR 0182577, doi:10.1007/BF02760024 .
Nešetřil, J.; Poljak, S. (1985), «On the complexity of the subgraph problem», Commentationes Mathematicae Universitatis Carolinae, 26 (2): 415–419 .
Östergård, P. R. J. (2002), «A fast algorithm for the maximum clique problem», Discrete Applied Mathematics, 120 (1–3): 197–207, doi:10.1016/S0166-218X(01)00290-6 .
Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A. (1997), «DNA solution of the maximal clique problem», Science, 278 (5337): 446–449, PMID 9334300, doi:10.1126/science.278.5337.446 .
Pardalos, P. M.; Rogers, G. P. (1992), «A branch and bound algorithm for the maximum clique problem», Computers & Operations Research, 19 (5): 363–375, doi:10.1016/0305-0548(92)90067-F .
Razborov, A. A. (1985), «Lower bounds for the monotone complexity of some Boolean functions», Proceedings of the USSR Academy of Sciences (em russo), 281: 798–801. English translation in Sov. Math. Dokl. 31 (1985): 354–357 .
Régin, J.-C. (2003), «Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003», Springer-Verlag, Using constraint programming to solve the maximum clique problem, Lecture Notes in Computer Science, 2833, pp. 634–648 .
Robson, J. M. (1986), «Algorithms for maximum independent sets», Journal of Algorithms, 7 (3): 425–440, doi:10.1016/0196-6774(86)90032-5 .
Robson, J. M. (2001), Finding a maximum independent set in time O(2n/4) .
Rosgen, B; Stewart, L (2007), «Cópia arquivada», Discrete Mathematics and Theoretical Computer Science, 9 (1): 127–136, consultado em 12 de dezembro de 2011, cópia arquivada em |arquivourl= requer |arquivodata= (ajuda) 🔗 .
Sipser, M. (1996), Introduction to the Theory of Computation, ISBN 053494728X, International Thompson Publishing .
Tarjan, R. E.; Trojanowski, A. E. (1977), «Finding a maximum independent set» (PDF), SIAM Journal on Computing, 6 (3): 537–546, doi:10.1137/0206038 ^{[ligação inativa]}.
Tomita, E.; Kameda, T. (2007), «An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments», Journal of Global Optimization, 37 (1): 95–111, doi:10.1007/s10898-006-9039-7 .
Tomita, E.; Seki, T. (2003), «Discrete Mathematics and Theoretical Computer Science», ISBN 978-3-540-40505-4, Springer-Verlag, An efficient branch-and-bound algorithm for finding a maximum clique, Lecture Notes in Computer Science, 2731, pp. 278–289, doi:10.1007/3-540-45066-1_22 |capítulo= ignorado (ajuda).
Tomita, E.; Tanaka, A.; Takahashi, H. (2006), «The worst-case time complexity for generating all maximal cliques and computational experiments», Theoretical Computer Science, 363 (1): 28–42, doi:10.1016/j.tcs.2006.06.015 .
Tsukiyama, S.; Ide, M.; Ariyoshi, I.; Shirakawa, I. (1977), «A new algorithm for generating all the maximal independent sets», SIAM Journal on Computing, 6 (3): 505–517, doi:10.1137/0206036 .
Valiant, L. G. (1983), «Proc. 15th ACM Symposium on Theory of Computing», ISBN 0897910990, Exponential lower bounds for restricted monotone circuits, pp. 110–117, doi:10.1145/800061.808739 |capítulo= ignorado (ajuda).
Vassilevska, V.; Williams, R. (2009), «Proc. 41st ACM Symposium on Theory of Computing», ISBN 9781605585062, Finding, minimizing and counting weighted subgraphs, pp. 455–464, doi:10.1145/1536414.1536477 |capítulo= ignorado (ajuda).
Wegener, I. (1988), «On the complexity of branching programs and decision trees for clique functions», Journal of the ACM, 35 (2): 461–472, doi:10.1145/42282.46161 .
Yuster, R. (2006), «Finding and counting cliques and independent sets in r-uniform hypergraphs», Information Processing Letters, 99 (4): 130–134, doi:10.1016/j.ipl.2006.04.005 .
Zuckerman, D. (2006), «Proc. 38th ACM Symp. Theory of Computing», ISBN 1595931341, Linear degree extractors and the inapproximability of max clique and chromatic number, pp. 681–690, doi:10.1145/1132516.1132612, Predefinição:ECCC |capítulo= ignorado (ajuda).