Defesa de Tese de Doutorado de Samuel Eduardo da Silva, 13/03/26, 10h, na sala 310 do Instituto de Computação e por videoconferência
Link para defesa: https://meet.google.com/ewn-givs-hzq?pli=1&authuser=5
Computing Treewidth: Decoders, Metaheuristics, Applications and Related Problems
Resumo:
A treewidth de um grafo é um parâmetro importante na teoria dos grafos que visa medir a semelhança de um grafo a uma árvore, ou seja, é uma medida da distância de G ser uma árvore. Várias classes de grafos têm treewidth limitada por uma constante, e muitos problemas NP-difíceis podem ser resolvidos em tempo polinomial em classes de grafos com treewidth limitada. Focamos na computação da treewidth. Dado um grafo G = (V,E) e denotando por CG a família de grafos cordais (triangulações) G′ tal que V(G) = V(G′) e E(G) ⊆ E(G′), a treewidth de um grafo G pode ser definida alternativamente como o tamanho do maior clique mínimo de um grafo em CG, menos um. Além disso, qualquer decomposição em árvore T de um grafo G′ ∈ CG também é uma decomposição em árvore de G. Primeiro, interessamos no principal subproblema a ser resolvido pelas heurísticas mais populares para a computação da treewidth, chamado Tree Decomposition Decoding. Nesse problema, temos um grafo G = (V, E) e uma permutação ρ de V(G) e devemos determinar a largura da decomposição em árvore T de G que é uma decomposição em árvore ótima da triangulação mínima G′ ∈ CG com ρ como ordenação de eliminação perfeita. Desenvolvemos dois algoritmos para Tree Decomposition Decoding. Juntamente com isso, introduzimos um Algoritmo Genético Tendencioso de Chaves Aleatórias (BRKGA) especialmente adaptado para a computação da treewidth, que usa um dos algoritmos propostos como subrotina. Além disso, propusemos outro BRKGA para abordar um problema relacionado, chamado Chordal Completion. Baseando-se em nossas descobertas, também estamos introduzindo um novo problema denominado Upper-Treewidth. Esse problema envolve determinar a ordenação de eliminação perfeita ρ de um grafo G que gera uma decomposição em árvore de largura máxima. Ao introduzir o Upper-Treewidth, visamos explorar novas dimensões no estudo da treewidth e fornecer insights mais profundos sobre as propriedades estruturais dos grafos. Fornecemos sua caracterização e provamos sua NP-completude. Essa investigação nos levou a definir uma nova classe de grafos chamada grafos bem-decompostos, nos quais o valor encontrado para treewidth é igual ao valor encontrado para Upper-Treewidth. Além disso, demonstramos os resultados da computação da treewidth em instâncias específicas de grafos do mundo real.
Abstract:
The treewidth of a graph is an important parameter in graph theory that aims to measure the tree-likeness of a given graph G, i.e., it is a measure of distance from G being a tree. Several classes of graphs have treewidth bounded by a constant, and many NP-hard problems can be solved in polynomial time in classes of graphs with bounded treewidth. We focus on the treewidth computation. Given a graph G = (V,E) and denoting by CG the family of chordal graphs (triangulations) G′ such that V(G) = V(G′) and E(G) ⊆ E(G′), the treewidth of a graph G can be defined alternatively as the size of the smallest maximum clique of a graph in CG, minus one. In addition, any tree decomposition T of a graph G′ ∈ CG is also a tree decomposition of G. First, we are interested in the main subproblem to be solved by the most popular heuristics for treewidth computation, called Tree Decomposition Decoding. In such a problem, we are given a graph G = (V, E) and a permutation ρ of V(G) and asked to determine the width of the tree decomposition T of G that is an optimum tree decomposition of the minimal triangulation G′ ∈ CG having ρ as perfect elimination ordering. We have developed two algorithms for Tree Decomposition Decoding. Alongside this, we introduced a Biased Random-Key Genetic Algorithm (BRKGA) tailored specifically for treewidth computation, that uses as a subroutine one of the algorithms proposed. Additionally, we proposed another BRKGA to address a related problem, called Chordal Completion. Building on our findings, we are also introducing a novel problem termed Upper-Treewidth. This problem involves determining the perfect elimination ordering ρ of a graph G that generates a tree decomposition of maximum width. By introducing Upper-Treewidth, we aim to explore new dimensions in the study of treewidth and provide deeper insights into the structural properties of graphs. We provide its characterization and prove its NP-completeness. This investigation led us to define a new class of graphs called well-decomposed graphs, in which the value found for treewidth equals the value found for Upper-Treewidth. Furthermore, we demonstrate the results of treewidth computation in specific real-world graph instances.
Banca examinadora:
Prof. Uéverton dos Santos Souza, UFF – Presidente
Prof. Luís Felipe Ignácio Cunha, UFF
Prof. Igor Machado Coelho, UFF
Prof. Pedro Henrique González Silva, UFRJ
Prof. Rian Gabriel Santos Pinheiro, UFAL