Algoritmos de aproximação e parametrizados para problemas de conectividade de pares

Author(s)

Marcelo Pinheiro Leite Benedito

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2023-08-16

Examining board members

Lehilton Lelis Chaves Pedrosa; Uéverton dos Santos Souza; Mário César San Felice; Santiago Valdés Ravelo; Orlando Lee

• Advisor: Lehilton Lelis Chaves Pedrosa

Abstract

In this thesis, we deal with a series of pair connectivity problems in graphs, whose input includes a set of pairs of vertices, called demands, and a solution consists of some structure connecting the demands. The problems are studied from the point of view of approximation and parameterized algorithms, which are combined to overcome hardness barriers coming from using each approach separately. Our results leverage both existing ideas, such as frameworks for dynamic programming over a tree decomposition, and novel techniques that generalize to related problems. In the Star k-Hub Center (SkHC), we are given a graph with a special center vertex and an integer k, and the task is to select a set of k vertices, called hubs, so that each vertex is connected to one hub. The goal is to minimize the length of the longest path connecting each pair of vertices through the center and assigned hubs. We initiate the study of parameterized algorithms for SkHC, giving the first hardness results on structural graph parameters and presenting an efficient parameterized approximation scheme with treewidth as parameter, that is, an algorithm that runs in time O^*((tw/?)^O(tw)) and produces a solution whose cost is within a factor 1 + ? of the optimal value. In the Multiple Allocation k-Hub Center (MAkHC), we are given a graph, whose vertices can be clients or hub locations, a set of demands composed by pairs of clients and an integer k. The task is to select k vertices minimizing the length of the longest path connecting the vertices of a demand through the assigned hub. We also initiate the study of this problem under the lens of parameterized complexity, giving inapproximability lower bounds and a reduction that rules out algorithms for several parameters. Our main result for MAkHC is a (2 + ?)-approximation parameterized by the treewidth of the graph, using techniques to remove dependency on extra parameters and to deal with arbitrary sets of demands. In the Spanning Tree-Star (STS), we are given a graph with two edge-cost functions, and a solution is a spanning connected subgraph. The goal is to minimize the sum of the edge costs in a solution, where pendant and non-pendant edges are charged differently. We also consider variants of STS where non-pendant edges of a solution induce a path or a cycle. We give improved algorithms for STS and variants, parameterized by treewidth or pathwidth, running in single-exponential time. These results rely on rank-based techniques and a new flexible label modeling of the problems (AU)

• FAPESP's process: 19/10400-2 - Approximation and parameterized algorithms for pair connectivity problems
• Grantee: Marcelo Pinheiro Leite Benedito
• Support Opportunities: Scholarships in Brazil - Doctorate