Two Dependency Constrained Spanning Tree Problems


We introduce two spanning tree problems with dependency constraints, where an edge can be chosen only if emph{at least} one or emph{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 a chordal cactus 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 $ln n$ factor, unless $P=NP,$ and that they are $W[2]$-hard. On the other hand, we present some polynomial cases. We test ILP formulations based on DCUT and MTZ constraints. Computational experiments are reported.


Palestra: "Two Dependency Constrained Spanning Tree Problems"

  • Luiz Alberto do Carmo Viana
  • Sala 04
  • 02 horas