Defesa de Proposta de Tese de Doutorado de Samuel Eduardo da Silva, em 12/08/2024, às 11:00 horas, 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
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.
The next step we want to take is to investigate the potential hybridization of tools we have for computing treewidth, especially for larger instances. The idea is to use BRKGA, which generates multiple tree decompositions during its processing. We also know many problems admit an FPT-algorithm parameterized by treewidth, such as Vertex Cover. Therefore, we want to verify whether stopping BRKGA processing at a relatively small treewidth found during its operation and applying an exact algorithm based on this solution would be efficient compared to direct applications of exact and metaheuristic methods.
Resumo:
A treewidth de um grafo é um parâmetro importante na teoria dos grafos que visa medir a semelhança de árvore de um grafo dado G, 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.
O próximo passo que queremos dar é investigar a potencial hibridização das ferramentas que temos para computar treewidth, especialmente para instâncias maiores. A ideia é usar o BRKGA, que gera várias decomposições em árvore durante seu processamento. Também sabemos que muitos problemas admitem um algoritmo FPT parametrizado por treewidth, como o Vertex Cover. Portanto, queremos verificar se parar o processamento do BRKGA em uma treewidth relativamente pequena, encontrada durante sua operação, e aplicar um algoritmo exato com base nessa solução, seria eficiente em comparação com aplicações diretas de métodos exatos e metaheurísticos.
Banca examinadora:
Prof. Uéverton dos Santos Souza, UFF – Presidente
Prof. Igor Machado Coelho, UFF
Prof. Pedro Henrique González Silva, UFRJ