Um estudo computacional sobre o problema de decomposição de grafos em árvore

Abstract

The notion of Tree Decomposition was introduced by Robertson and Seymour in their seris of articles about graph minors and can be intuitively seen as an organization of the vertices and edges of the graph in a tree structure, being the treewidth equal to the size of the largest subset of vertices minus one. The minimum treewidth over all tree decompositions of a graph gives us the treewidth of the graph. Many hard problems can be polinomially solved for a graph G if a tree decomposition with bounded treewidth of G is given. For instance, hamiltonian cycle, maximum independent set isomorphism, vertex coloring, etc. The complexity of the algorithm that solves such problems are generally exponential on the width of the given tree decomposition. So, we can expect that finding a tree decomposition of minimum width is hard. In fact, Arnborg, Corneil and Proskurowski [2] showed that the problem os NP-hard. The problem of finding the treewidth of a graph is the subject of this thesis. The decision variation of the problem is, given a graph G and for a fixed integer k, deciding if the treewidth of G is at most k. We discuss a proof that the decision problem can be polynomially solved. In the last decade were proposed many heuristics for computing upper bounds [3, 10], lower bounds [6, 8, 11], enumeration methods [5] and approximative algorithms [1, 7, 4]. However, none of these results can be considered as good ones, since there is no benchmarks for with the treewidth is known, as well as the difference between the lower and upper bounds for the existing benchmarks is very large. Additionally, the enumeration method was showed to be inefficient even for the decision problem with k fixed in small values (e.g., k = 4) [12]. So, we propose another enumeration method for the problem that can be used along with branch and bound techniques. Actually, we work with the triangulation problem that is equivalent to the tree decomposition problem. We propose a new representation of a solution, wich uses the concept of total orders. Once a solution ca be represented like that, an algorithm that enumerates all the total extensions of a given partial order can be used to enumerate all solutions for the tree decomposition problem, as long as we offer the partial order containing only the reflexive pairs vv, where v is a vertex of the input graph. The proposed enumeration method is a modification of the Corrêa and Szwarcfiter algorithm [9]. This modification allows only the total extensions to be enumerated. The algorithm presents two principal advantages over the Bodlander and Kloks method: it can be used in conjunction with the Branch and Bound method; and it can enumerate a subspace of solutions, what can be useful if we know some existing relations in an optimal solution, or even to investigate such subspaces in order to characterize them. We have implemented and tested the proposed algorithm, applying the branch and bound method and restricting the subspace of solutions. The partial orders used to define the explored subspaces were obtained based on the labeling heuristics for finding upper bounds. Unfortunately, we did not obtain good results because, even when we restricted the subspace of solutions to be searched, the number of nodes generated in the branch and bound tree was too large, exceeding the machine’s memory capacity. In the text, we also present the proof of the NP-hardness of the problem, an algorithm to compute an optimal decompostion of a chordal graph, and also the many existing heuristics to compute lower and upper bounds. In addition, we implemented and tested the labeling heuristics for upper bounds and a GRASP heuristic, being the first application of a GRASP meta-heuristic to the problem.