TY - JOUR
AU - Viana, Luiz Alberto
AU - Campêlo, Manoel
PY - 2017/07/02
TI - The Least-Dependency Constrained Spanning Tree Problem
JF - Anais do Encontro de Teoria da Computação (ETC); 2017: Anais do II Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2017.3190
KW -
N2 - 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.
UR - https://sol.sbc.org.br/index.php/etc/article/view/3190