Defesa de Dissertação: Rodrigo Nogueira Lima David
Data da publicação: 28 de fevereiro de 2025 Categoria: Defesas de Dissertação, NotíciasTítulo: Hard Instances for the Maximum Clique Problem with High Probability
Data: 07/03/2025
Horário: 14h
Local: Sala de Reuniões – Bloco 910
Resumo:
The Maximum Clique problem is a classic graph-theoretical optimization problem with the objective of finding a maximum clique in a given input graph. 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 & Bound algorithms for solving Maximum Clique and how they make the problem more tractable in practice. We approach the relationship between cliques and proper vertex colorings and derive the asymptotic growth of the number of colorings in random graphs with high probability. Using this result paired with a coloring-to-clique polynomial reduction in the literature, we generate new Maximum Clique instances and analyze them. Moreover, we examine a family of instances from the literature that induce exponential runtime on a widely adopted subclass of Branch & Bound algorithms that use a chromatic upper bound to prune branches. We propose a preprocessing method that enables these algorithms to solve such instances in linear time on their size. Furthermore, we introduce a randomized construction that produces graphs resistant to this preprocessing and still exhibit exponential runtime for these algorithms, even if the upper bound uses the fractional chromatic number instead, which is a tighter bound. Finally, we run some computational tests to validate our analyses.
Banca examinadora:
- Prof. Dr. Victor Almeida Campos (MDCC/UFC – Orientador)
- Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC)
- Prof. Dr. Wladimir Araújo Tavares (UFC)
- Prof. Dr. Fabrício Siqueira Benevides (UFC)
- Prof. Dr. Guilherme Oliveira Mota (IME/USP)