The Least-Dependency Constrained Spanning Tree Problem

• Luiz Alberto Viana UFC
• Manoel Campêlo UFC

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.

Referências

Darmann, A., Pferschy, U., Schauer, J., and Woeginger, G. J. (2011). Paths, trees and matchings under disjunctive constraints. Discrete Applied Math., 159(16):1726 – 1735.

Douglas, B. (2001). West. Graph Theory. Prentice Hall, Upper Saddle River, NJ.

Gary, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness.

Samer, P. and Urrutia, S. (2015). A branch and cut algorithm for minimum spanning trees under conflict constraints. Optimization Letters, 9(1):41–55.

Viana, L. A. (2016). Árvore geradora com dependências mínima. Master’s thesis, Federal University of Ceará.

Zhang, R., Kabadi, S., and Punnen, A. (2011). The minimum spanning tree problem with conflict constraints and its variations. Discrete Optimization, 8(2):191 – 205.