%A Viana, Luiz Alberto
%A Campêlo, Manoel
%D 2017
%T The Least-Dependency Constrained Spanning Tree Problem
%K
%X We introduce the Least-Dependency Constrained Spanning Tree Problem, which consists of finding a spanning tree where each edge has at least one edge of its dependency set, if non-empty, also in the tree. The dependencies on the input graph G are described by a digraph D where the vertices are the edges of G, and the in-neighbors of a vertex are its dependency set. We show that the optimization problem is NP-hard even if G is a chordal cactus with maximum degree 3 or diameter at most 2, and D is a disjoint union of arborescences of height 2. The same complexity is proved when G is planar bipartite, and each component of D is an oriented cycle or an anti-arborescence of height 1. We also report two polynomial cases.
%U https://sol.sbc.org.br/index.php/etc/article/view/3190
%J Anais do Encontro de Teoria da Computação (ETC)
%0 Journal Article
%R 10.5753/etc.2017.3190
%P 53-56%@ 2595-6116
%8 2017-07-02