Um novo majorante para o número de independência de um grafo obtido por técnicas de programação quadrática

Abstract

Introduz-se um novo majorante para o número de independência de um grafo que pode ser calculado resolvendo um problema de Programação Quadrática Convexa com restrições de não negatividade. Provam-se diversas propriedades daquele majorante, uma das quais permite estabelecer que ele constitui uma generalização do majorante introduzido por A. J. Hoffman e L. Lovász para o número de independência de grafos regulares. Caracteriza-se também a classe de grafos para os quais o novo majorante iguala o número de independência, referem-se alguns casos em que os respectivos conjuntos independentes máximos são fáceis de obter e descreve-se uma metodologia que permite reconhecer os grafos daquela classe. Seguidamente, desenvolve-se um algoritmo específico para resolver o problema quadrático com restrições de não negatividade associado ao novo majorante. Assim, apresenta-se, primeiro, um algoritmo para Programação Linear que combina o algoritmo dual-afim com mudanças de escala com o método do gradiente projectado. Estende-se, depois, este procedimento à Programação Quadrática Convexa e particulariza-se o algoritmo resultante para a resolução do problema quadrático anteriormente mencionado. Por fim, apresenta-se um algoritmo polinomial para resolver aproximadamente o problema da determinação de um conjunto independente máximo de um grafo arbitrário. A heurística proposta baseia-se numa propriedade do novo majorante e utiliza o algoritmo desenvolvido para o problema quadrático que lhe está associado. Apresentam-se igualmente os resultados computacionais da aplicação desta heurística a 42 grafos-teste da colecção DIMACS.

A new upper bound on the independence number of a graph that can be computed by solving a Convex Quadratic Programming problem with nonnegativity constraints is introduced. Several properties of this upper bound are proven one of which allows us to state that it constitutes a generalization of the bound introduced by A. J. Hoffman and L. Lovasz for regular graphs. The class of graphs that attain the proposed bound is characterized, as well as several particular cases in which the independence number is easily determined. A methodology for recognizing the referred class is also described. Subsequently, a specific algorithm for solving the quadratic programming problem with nonnegativity constraints associated to the new upper bound is developed. Thus, an algorithm for Linear Programming that combines the dual affine scaling algorithm with the gradient projected method is introduced first. Then an extension of this procedure to Convex Quadratic Programming is provided and a particular version of the resulting algorithm, applicable to the above mentioned quadratic problem, is given. Finally, a polynomial algorithm for approaching the maximum independent set of an arbitrary graph is presented. The proposed heuristic is based on a property of the new upper bound and uses the developed algorithm for solving the associated quadratic problem. The results of computational experiments for this heuristic carried out on 42 DIMACS clique benchmark instances are also reported.