Two dependency constrained spanning tree problems

摘要

We introduce two spanning tree problems with dependency constraints, where an edge can be chosen only if at least one or all edges in its dependency set are also chosen, respectively. The dependencies on the input graph G are described by a digraph D whose vertices are the edges of G, and the in-neighbors of a vertex are its dependency set. We show that both problems are NP-hard even if G is an outerplanar chordal graph with diameter 2 or maximum degree 3, and D is a disjoint union of arborescences of height 2. We also prove that the problems are inapproximable to a lnn factor, unless P=NP, and that they are W[2]-hard. As an attempt to narrow the hardness gap, we present two polynomial cases. We test integer linear programming formulations based on directed cut (DCUT) and Miller-Tucker-Zemlin (MTZ) constraints. Computational experiments are reported.