Given a graph $G$ and a digraph $D$ whose vertices are the edges of $G$, we investigate the problem of finding a spanning tree of $G$ that satisfies the constraints imposed by $D$. The restrictions to add an edge in the tree depend on its neighborhood in $D$. Here, we generalize previously investigated problems by also considering as input functions $\ell$ and $u$ on $E(G)$ that give a lower and an upper bound, respectively, on the number of constraints that must be satisfied by each edge. The produced feasibility problem is denoted by \texttt{ G-DCST}, while the optimization problem is denoted by \texttt{ G-DCMST}. We show that \texttt{ G-DCST} is NP-complete even under strong assumptions on the structures of $G$ and $D$, as well as on functions $\ell$ and $u$. On the positive side, we prove two polynomial results, one for \texttt{ G-DCST} and another for \texttt{ G-DCMST}, and also give a simple exponential-time algorithm along with a proof that it is asymptotically optimal under the \ETH. Finally, we prove that other previously studied constrained spanning tree (\textsc{ CST}) problems can be modeled within our framework, namely, the \textsc{ Conflict CST}, the \textsc{ Forcing CS, the \textsc{ At Least One/All Dependency CST}, the \textsc{ Maximum Degree CST}, the \textsc{ Minimum Degree CST}, and the \textsc{ Fixed-Leaves Minimum Degree CST}.
Categories: cs.CC