Defesa de Qualificação de Mestrado: Rodrigo Nogueira Lima David
Data da publicação: 9 de setembro de 2024 Categoria: Notícias, Qualificação de Mestrado
Título: Hard Instances for the Maximum Clique Problem with High Probability
Data: 16/09/2024
Horário: 14h
Local: Sala de Seminários – Bloco 952
Resumo:
The Maximum Clique problem is a classic graph-theoretical optimization problem with the objective of finding a maximum clique in a given graph G. Despite numerous theoretical hardness results, empirical studies suggest that the problem is often easier than expected. In this work, we explore a class of Branch and Bound algorithms for solving Maximum Clique and demonstrate how these algorithms can make the problem more tractable in practice. We analyze the relationship between cliques and (proper vertex) colorings, investigating the hardness difference in enumerating these structures; particularly, we derive the asymptotic growth of the number of colorings in random graphs with high probability. Moreover, using a coloring-to-clique reduction in the literature, we generate Maximum Clique instances and compare them to random graphs of different densities. Additionally, we examine a family of instances from the literature that induce exponential runtime on a widely adopted subclass of Branch & Bound algorithms. We propose a pre-processing method that enables these instances to be solved in polynomial time. Furthermore, we introduce a randomized construction that produces instances resistant to this pre-processing and still exhibit exponential runtime for the aforementioned algorithms.
Banca examinadora:
- Prof. Dr. Victor Almeida Campos (MDCC/UFC – Orientador)
- Prof. Dr. Wladimir Araújo Tavares (UFC)
- Prof. Dr. Fabrício Siqueira Benevides (UFC)
- Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC)
