Defesa de Dissertação de Mestrado de Edmundo Pinto Neto, em 08/12/2023, às 09:30 horas, na sala 206 do Instituto de Computação
Minimizando Distâncias entre Vértices e Arestas através de Árvores t-Geradoras em Grafos
Resumo:
Uma árvore t-geradora de um grafo G é uma árvore geradora T de G na qual quaisquer dois vértices adjacentes de G têm distância no máximo t em T. Dizemos que G é t-admissível se admite uma árvore t-geradora, e o σ(G) é o menor t tal que G seja t-admissível, chamado de índice de extensão de G. Decidir se G tem uma árvore t-geradora está em P para t≤2, é NP-completo para t≥4, e decidir a 3-admissibilidade é um problema em aberto há mais de 25 anos. Couto, Cunha e Posner definiram a árvore aresta t-geradora de um grafo, que é uma árvore T do grafo linha de G em que duas arestas adjacentes de G têm distância no máximo t em T. Quando se pretende minimizar as distâncias entre arestas, eles provaram que a 3-admissibilidade de arestas é um problema solucionável em tempo polinomial, enquanto é NP-completo para t≥8, mesmo para grafos bipartidos. Esta dissertação investiga a complexidade de lidar com distâncias minimizadas entre vértices e arestas ao mesmo tempo. Isso motiva o estudo do problema da ÁRVORE TOTAL ADMISSIBILIDADE, definido como a determinação de uma árvore t-geradora para um grafo total Tot(G), onde Tot(G) é o grafo de interseção dos vértices e arestas de G. Como contribuições, são apresentadas relações entre os índices de extensão de G, L(G) e Tot(G). Além disso, é provado que ÁRVORE TOTAL ADMISSIBILIDADE é NP-completo, mesmo para as classes de grafos bipartidos ou planares. Ademais, alguns subgrafos de grafos totais podem ser obtidos da seguinte forma: grafo-meio (middle graph) M(G) de G, obtido a partir do grafo linha de G, L(G), unindo aos vértices de G e tornando cada vértice recém inserido vizinho aos vértices de L(G) que compartilham rótulo; grafo-quase-total QT(G) de G, obtido subdividindo cada aresta de G exatamente uma vez e adicionando as arestas originais de G novamente. Essas duas classes anteriores, como várias outras classes clássicas de grafos, podem ser vistas como pertencentes a classe de grafos clique-aumentantes, obtidas de um grafo G escolhendo cliques arbitrárias de G e para cada clique, adicionando um vértice simplicial. Este trabalho mostra uma série de propriedades relativas a construções especiais, casos tratáveis e provas de NP-completude da ADMISSIBILIDADE para grafos clique-aumentantes.
Abstract:
A t-spanning tree of a graph G is a spanning tree T of G in which any two adjacent vertices of G have distance at most t in T. We say that G is t-admissible if it admits a t-spanning tree, and the σ(G) is the smallest t such that G is t-admissible, called the stretch index of G. Deciding whether G has a t-spanning tree is in P for t≤2, is NP-complete for t≥4, and Deciding 3-admissibility has been an open problem for more than 25 years. Couto, Cunha and Posner defined the edge tree t-spanner of a graph, which is a spanner tree T of the line graph of G in which two adjacent edges of G have distance at most t in T. When we want to minimize the distances between edges, they proved that the edge 3-admissibility is a polynomial-time solvable problem, while it is NP-complete for t≥8, even for bipartite graphs. This dissertation investigates the complexity of dealing with minimized distances between vertices and edges at the same time. This motivates the study of the TOTAL TREE ADMISSIBILITY problem, defined as determining a tree t-spanner with the lowest t for a total graph Tot(G), where Tot(G) is the intersection graph of the vertices and edges of G. As contributions, relationships are presented between the stretch indexes of G, L(G) and Tot(G). Furthermore, it is proved that TOTAL TREE ADMISSIBILITY is NP-complete, even for the classes of bipartite or planar graphs. Moreover, some subgraphs of total graphs can be obtained as follows: middle graph M(G) of G, obtained from the line graph of G, L(G), joining the vertices of G and making each newly inserted vertex neighboring the vertices of L(G) that share label; almost-total graph AT(G) of G, obtained by subdividing each edge of G exactly once and adding the original edges of G again. These two previous classes, like several other classical classes of graphs, can be seen as belonging to the class of clique-augmenting graphs, obtained from a graph G by choosing arbitrary cliques of G and for each clique, adding a simplicial vertex. This work shows a series of properties relating to special constructions, tractable cases and NP-completeness proofs of ADMISSIBILITY for clique-augmenting graphs.
Banca examinadora:
Prof. Luís Felipe Ignácio Cunha, UFF
Prof. Uéverton dos Santos Souza, UFF
Prof. Fábio Protti, UFF
Prof.ª Celina Miraglia Herrera de Figueiredo, UFRJ