What are the advantages/inconveniences compared to a standard topological sort algorithm ?
What's challenging about dependency resolution is handling the versioning constraints. For example, you may state that your project is dependent on the following packages {"A:1.0", "B:[2.0,)", "C:3.2"}. Resolving a dependency is simply selecting one version of each package. At first glance this is easy. However, you need to consider the transitive dependencies of each package. Meaning, A:1.0 will have set of dependencies you need to resolve. Then B:2.0, B:2.1, etc will have their own set of dependencies. In some cases you may find that there is simply no means to resolve the dependencies.
For example, if A:1.0 depended on C:2.1, there would be no way to resolve your transitive dependency graph.
Currently, most package managers use a heuristic based backtracking approach. However, there has been a recent push to using SAT solvers. It's a fascinating and messy area.
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.