Título: The Generalized Dependency Constrained Spanning Tree Problem

Data: 30/09/2019

Horário: 10:00h

Local: Sala de Seminários - Bloco 952

Resumo:

We introduce the Generalized Dependency Constrained Spanning Tree Problem (G-DCST), where an edge can be chosen only if the number of edges chosen from its dependency set lies in a certain interval. The dependency relations between the edges of the input graph G are described by the input digraph D, whose vertices are the edges of G. The in-neighbors of a vertex of D form its dependency set. We show that G-DCST unifies and generalizes some known spanning tree problems that apply conflict constraints over edges or lower and upper bounds on vertex degrees. We show that the feasibility version of G-DCST is NP-complete even under strong restrictions on the structures of G and D as well as on the functions that define the minimum or maximum number of dependencies to be satisfied. We also show that this problem keeps an ln n inapproximability threshold under tight assumptions over G and D. On the other hand, we spot a polynomial case via a matroid intersection argument.

Banca:

• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
• Prof. Dra. Claudia Linhares Sales (MDCC/UFC)
• Prof. Dra. Ana Shirley Ferreira da Silva (UFC)