Problems on spanners in graphs

Abstract

The objective of this project is to study problems concerning graph spanners. Given a connected graph G and a positive real number t > 1 (stretch factor), a t-spanner of G is a spanning subgraph H of G such that for every pair of vertices u and v, the distance between u and v in H is at most t times the distance between them in G. A central problem about spanners, known as the tree t-spanner problem, asks to find, given a connected graph G, a tree that is a t-spanner of G, or conclude that such tree does not exist. When the objective is to find a t-spanner subgraph with the minimum number of edges, we obtain the minimum t-spanner problem. For fixed t, the case t = 3 is the only one for which the computational complexity has not been established yet. In this project our aim is to study problems involving graph spanners, with focus on their algorithmic aspect and computational complexity. We are interested in discovering new classes of graphs, for which those problems are polynomially solvable. Also, we will focus on the case t = 3. We plan to investigate these problems with new approaches (approximation algorithms or exact methods) to contribute with algorithmic and complexity results that advance the state of the art of this field. (AU)