Defesa de Dissertação de Mestrado de Kedson Alves Silva, em 08/07/2024, às 15:00 horas, 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
An Investigation of Clique Cover on ⌞-EPG Representations and Related Problems
Resumo:
Clique Cover é um problema clássico da teoria dos grafos no qual é dado um grafo G = (V,E), um número inteiro k, e é perguntado se V(G) pode ser dividido em no máximo k cliques. grafos EPG (Edge intersection graphs of paths on a grid) são grafos cujos vértices podem ser representados como caminhos não triviais em uma grade, de modo que dois vértices são adjacentes se e somente se os caminhos correspondentes compartilham pelo menos uma aresta da grade. Chamamos as representações desses grafos por meio de caminhos em uma grade de representações EPG. Quando os caminhos possuem no máximo uma mudança de direção (dobra), esses grafos são chamados de grafos B1-EPG, e são grafos ⌞-EPG (ou grafos com caminhos em forma de ⌞) se todos os caminhos forem representados com uma das seguintes formas: ” ⌞ “, ” – “, ou ” | “. A classe de grafos ⌞-EPG é uma subclasse dos grafos B1-EPG e uma superclasse natural de grafos de intervalo. Sabemos que todas as cliques maximais de um grafo B1-EPG podem ser calculadas em tempo polinomial e que o problema Clique Cover em grafos de intervalo é solucionável em tempo polinomial. Levando isso em consideração, neste trabalho estudamos a complexidade do problema Clique Cover em grafos ⌞-EPG. Mostramos que, dada uma representação ⌞-EPG de um grafo G, é NP-completo determinar se V(G) pode ser dividido em no máximo k cliques, mas pode ser resolvido em tempo FPT quando parametrizado por k. Além disso, apresentamos um algoritmo de 2-aproximação para Clique Cover Mínimo em uma representação ⌞-EPG. Adicionalmente, adaptamos ambos os algoritmos para o caso em que a entrada é um grafo sem sua representação ⌞-EPG. Também mostramos que Clique Cover em representações ∂EPG2 (uma classe particular de representações ⌞-EPG) é solucionável em tempo polinomial. Por fim, demonstramos que o problema Feedback Vertex Set é NP-completo em representações ⌞-EPG, e que Caminho Hamiltoniano e Ciclo Hamiltoniano são NP-completos em grafos ⌞-EPG.
Abstract:
Clique Cover is a classical graph theory problem where we are given a graph G = (V,E), an integer k, and asked if V(G) can be partitioned into at most k cliques. EPG graphs (Edge intersection graphs of paths on a grid) are graphs whose vertices can be represented as nontrivial paths on a grid such that two vertices are adjacent if and only if the corresponding paths share at least one edge of the grid. We refer to the representations of these graphs through paths on a grid as EPG representations. When the paths have at most one change of direction (bend), these graphs are called B1-EPG graphs, and they are ⌞-EPG graphs (or graphs with paths in the shape of ⌞) if all paths are represented in one of the following forms: “⌞”, “-“, or “|”. The class of ⌞-EPG graphs is a subclass of B1-EPG graphs and a natural superclass of interval graphs. We know that all maximal cliques of a B1-EPG graph can be computed in polynomial time and that the Clique Cover problem in interval graphs is solvable in polynomial time. Taking this into consideration, in this work, we investigate the complexity of the Clique Cover problem in ⌞-EPG graphs. We show that given an ⌞-EPG representation of a graph G, it is NP-complete to determine whether V(G) can be partitioned into at most k cliques, but it can be solved in FPT time when parameterized by k. In addition, we present a 2-approximation algorithm for the minimum clique cover of an ⌞-EPG representation. Additionally, we adapt both algorithms for the case where the input is a graph without its ⌞-EPG representation. Furthermore, we show that Clique Cover on ∂EPG2 representations (a particular class of ⌞-EPG representations) is solvable in polynomial time. Finally, we demonstrate that Feedback Vertex Set problem is NP-complete on ⌞-EPG representations, and that both Hamiltonian Path and Hamiltonian Cycle are NP-complete in ⌞-EPG graphs.
Banca examinadora:
Prof. Uéverton dos Santos Souza, UFF – Presidente
Prof. Fábio Protti, UFF
Prof. Tanilson Dias dos Santos, UFT
Prof. Janio Carlos Nascimento Silva, IFTO