Convexidade em grafos orientados e convexidade de ciclos

Abstract

The main focus of this work is the study of the computational complexity of determining some optimization parameters defined in the context of Convexity in directed and undirected Graphs. This thesis can be divided into two parts. The first part corresponds to the study of convexity problems in directed graphs. We observed that these problems have been little studied in the literature. Most of our results are related to the computational complexity of the interval number and hull number parameters for classes of directed graphs, in three convexities: geodesic convexity, two path convexity, and minimum two path convexity. We show results that exhibit the difficulty of determining these parameters even when the underlying graph of the given directed graph is restricted to particular subclasses such as split graphs, bipartite graphs, and chordal bipartite graphs. On the positive side, two path convexity and minimum two path convexity, the existence of cubic-time algorithms to determine them when the input is a directed graph with bounded clique-width, obtained by applying Courcelle’s Theorem. We also present some upper bounds for these parameters concerning the number of vertices of the given directed graph. In the second part of this thesis, we study the convexity of cycles in undirected graphs. This convexity was recently defined and is motivated by Knot Theory. The parameters we worked on were the convexity number and percolation time. We show that the problem of determining the convexity number is NP-complete and W [1]-hard parameterized by the size of the solution. Finally, in the search for a dichotomy regarding the percolation time of a graph, we first show that determining whether the percolation time in a graph is at least two can be computed in polynomial time. On the other hand, we prove that determining whether the percolation time is at least nine is NP-complete.