On two restricted ancestors tree problems

We consider rooted minimum spanning tree problems subject to allowed ancestor relations which follow from network security constraints. In one problem nodes are associated with security labels that impose father–child relations. We prove that the feasible solutions define a matroid. In the other problem, there are permission constraints which impose descendant–ancestor relations. We show that even simple special cases of this problem are not approximable within a sub-logarithmic factor, and describe a square root approximation when the edge weights satisfy the triangle inequality.