The Least-Dependency Constrained Spanning Tree Problem

• Luiz Alberto Viana
• Manoel Campêlo

DOI: https://doi.org/10.5753/etc.2017.3190

Resumo

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.