I think it's still NP-complete because you can still specify arbitrary dependency constraints. (Of course, just because it's NP-complete doesn't mean it's not tractable in practice for the kinds of instances that come up in real life.)