Busca em largura lexicográfica e algoritmos de solução exata para o problema da clique máxima

Abstract

Resumo: O problema da Clique Máxima (CM) é o problema de encontrar uma clique de tamanho máximo em um grafo dado. Existem algoritmos de solução exata que fazem uso da técnica de branch and bound para o CM que utilizam a coloração de vértices com menor número possível de cores como limitante superior. Assim como o CM, o problema de coloração de vértices é um problema difícil do ponto de vista computacional, contudo pode ser resolvido em complexidade de tempo linear quando restrito a certas classes de grafos. O algoritmo conhecido como Busca em Largura Lexicográfica (LexBFS) é capaz de produzir ordenações dos vértices de algumas classes de grafos que levam à solução de problemas difíceis em tempo polinomial. O objetivo deste trabalho é estudar algoritmos branch and bound que utilizam coloração de vértices na solução do CM, porém modificados com o Algoritmo LexBFS. Para avaliar tais modificações, foram empregados métodos da Análise de Experimental de Algoritmos. Com isso, foi possível fazer inferências sobre os resultados obtidos utilizando o método estatístico de teste de hipótese. A conclusão que se chega após a modificação com o Algoritmo LexBFS é que o espaço de busca necessário é menor, mas o tempo de execução é maior. Palavras-chaves: Busca em Largura Lexicográfica. Algoritmos para o Problema da Clique Máxima. Análise Experimental de Algoritmos.

Abstract: The Maximum Clique (MC) problem is the problem of finding a maximum size clique on a given graph. There are exact solution algorithms that use the branch and bound technique for MC and a coloring of graph vertices with as few colors as possible as the upper bound. As MC, the vertex coloring problem is a computationally difficult problem, however it can be solved in linear time complexity when restricted to certain graph classes. The algorithm known as Lexicographic Breadth-first Search (LexBFS) is capable of producing vertex ordering of some classes of graphs with properties that lead to the solution of difficult problems in polynomial time. The aim of this work is to study branch and bound algorithms that use vertex coloring to solve MC, but modified with the LexBFS algorithm. To evaluate such changes, methods of Experimental Analysis of Algorithms were used. Thus, it was possible to make inferences about the results obtained using the statistical method of hypothesis testing. The conclusion that is reached after the modification with the LexBFS algorithm is that, the search space is smaller, but the execution time was longer. Key-words: Lexicographic Breadth-first Search. Maximum Clique Problem Algorithms. Experimental Analysis of Algorithms.