Algoritmo de Enumeração de Clique

9

Estou lendo um artigo antigo do MC Golumbic sobre gráficos EPT (interseção de arestas de caminhos em uma árvore). No artigo, é mostrado que o número máximo de cliques de uma instância de gráfico EPT é polinomial. Conclui que, se um oracle relatar que um gráfico é um gráfico EPT, é possível encontrar o clique máximo com um algoritmo de enumeração de clique padrão.G

Primeiro de tudo, quais são esses algoritmos de enumeração de clique padrão? Se houver mais de um, podemos dizer que, se o número máximo de cliques de um gráfico for polinomial, podemos usar algum desses algoritmos de enumeração? Ou devemos derivar um algoritmo especial de um algoritmo genérico que usa algumas estruturas especiais da classe de gráfico?

Desde já, obrigado.

ds.algorithms graph-algorithms clique Arman
fonte

Respostas:

13

Existem vários algoritmos sensíveis à saída para enumerar todas as cliques máximas em tempo polinomial por saída. Um dos algoritmos mais antigos foi desenvolvido por Tsukiyama, Ide, Ariyoshi e Shirakawa (1977).

  • Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi e Isao Shirakawa: um novo algoritmo para gerar todos os conjuntos independentes máximos. SIAM J. Comput. 6 (3): 505-517 (1977)

Isso significa que, se você sabe que seu gráfico tem no máximo muitas panelinhas máximas polinomialmente, o tempo total de execução de seu algoritmo será polinomial no tamanho da entrada.

Yoshio Okamoto
fonte
Infelizmente, não tenho acesso ao jornal. Mas tenho certeza de que é isso que estou procurando, obrigado.
Arman
4

O algoritmo de Bron – Kerbosch calcula todas as cliques máximas em um gráfico não direcionado (consulte Wikipediaeadia ). O pior caso de tempo de execução é O (3 n / 3 ), aparentemente é muito rápido em geral e ainda é o algoritmo mais rápido conhecido para calcular todos os cliques máximos. Para uma referência mais recente, consulte os documentos de V. Stix e Cazals e Karande .

Volker Turau
fonte
2
O(3n/3)3n/33n/3 cliques máximos (ou seja, K3,3,...,3)
Yoshio Okamoto
11
Para trabalhos mais recentes sobre Bron – Kerbosch, consulte meus artigos arxiv.org/abs/1006.5440 com Strash e Löffler no ISAAC 2010 e arxiv.org/abs/1103.0318 com Strash no SEA 2011. No entanto, isso realmente não responde à pergunta do pôster original como o algoritmo não é sensível à saída: pode levar um tempo exponencial mesmo quando há apenas polinomialmente muitas cliques máximas.
David Eppstein