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.
If conflicts are not possible, then it is not NP complete, toposort is good enough, and backtracking is unnecessary.
Conflicts between packages which are both maintained should not happen. If two packages want to provide the same file, Debian can install both and has tooling to switch between them.