Banca de QUALIFICAÇÃO: DANIEL DE GUSMÃO MORAES

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
STUDENT : DANIEL DE GUSMÃO MORAES
DATE: 06/11/2026
TIME: 09:00
LOCAL: Remoto
TITLE:

Generating Hard Instances of the Hamiltonian Cycle Problem via Degree Distribution Optimization


KEY WORDS:

Hamiltonian Cycle Problem, Instance Hardness, Surrogate Objective, Mixed-Integer Quadratic Programming


PAGES: 60
BIG AREA: Ciências Exatas e da Terra
AREA: Ciência da Computação
SUMMARY:

In this work, we investigate the Hamiltonian Cycle Problem (HCP) from the perspective of instance difficulty. Although no polynomial-time algorithm is known for NP-complete problems, state-of-the-art HCP algorithms efficiently solve most random instances, including those near the hamiltonicity phase transition. In contrast, the hardest known instances are highly structured, non-Hamiltonian, and dense. These instances were generated using expensive evolutionary algorithms that directly maximized the number of recursive calls made by a state-of-the-art HCP solver. While the instances can be reproduced once the underlying structure is known, this approach offers limited insight into what features drive hardness. We propose an efficient method for generating hard HCP instances by optimizing a surrogate objective based on degree distribution statistics. We introduce two approaches: (1) an exact MIQP model that maximizes degree variance alone, serving as a baseline, and (2) a heuristic (the VM Heuristic) that simultaneously maximizes variance and minimizes median degree using a multi-start hillclimber with edge swaps. Given a fixed number of vertices, the VM Heuristic reproduces all known hardest instances and generates new ones across a wide range of edge counts. Our analysis reveals a previously unreported threshold at m = 4(n - 3), where instances exhibit an abrupt change from low to high recursion counts, growing exponentially beyond this threshold. These results provide insight into the structural features that drive HCP hardness and enable efficient generation for future research.


COMMITTEE MEMBERS:
Presidente - 2859606 - SILVIA MARIA DINIZ MONTEIRO MAIA
Interno - 1702873 - MATHEUS DA SILVA MENEZES
Externo ao Programa - 1294916 - MADRAS VISWANATHAN GANDHI MOHAN - UFRNExterno à Instituição - ISLAME FELIPE DA COSTA FERNANDES - UFBA
Externo à Instituição - THIAGO SOARES MARQUES - UEPB
Notícia cadastrada em: 22/10/2026 14:02
SIGAA | Superintendência de Tecnologia da Informação - (84) 3342 2210 | Copyright © 2006-2026 - UFRN - sigaa12-producao.info.ufrn.br.sigaa12-producao