Comment by qznc

It is NP complete, if conflicts are possible. Is that what Molinillo means by a 'locking' dependency graph?

If conflicts are not possible, then it is not NP complete, toposort is good enough, and backtracking is unnecessary.