The Generalized Dependency Constrained Spanning Tree Problem
Luiz Alberto do Carmo Viana, Manoel Bezerra Campêlo · Electronic Notes in Theoretical Computer Science · 2019
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.