Dependency Resolution Algorithms

Updated

October 30, 2026

Dependency Resolution Algorithms

At first glance, resolving software dependencies sounds like a simple graph traversal problem: if package \(A\) needs package \(B\), install \(B\); if \(B\) needs \(C\), install \(C\).

However, in realistic operating systems, dependency resolution is formally an NP-complete problem equivalent to the Boolean Satisfiability Problem (SAT):

                      The Dependency Maze
                         +-------+
                         | App A |
                         +---+---+
                             |
             +---------------+---------------+
             v                               v
       +-----------+                   +-----------+
       | Lib X 2.0 |                   | Lib Y 1.4 |
       +-----+-----+                   +-----+-----+
             |                               |
             +---------------+---------------+
                             |
                             v
               CONFLICT: Which Lib Z to install?
               Lib X requires: Lib Z >= 3.0
               Lib Y requires: Lib Z < 2.5

Why Dependency Resolution is Hard

  1. Version Range Constraints: Packages declare dependencies with inequality constraints (>= 1.2, < 2.0, != 1.5.1).
  2. Package Conflicts (Conflicts / Breaks): Two packages cannot coexist simultaneously (e.g., mariadb and mysql, or busybox-coreutils and gnu-coreutils).
  3. Virtual Provides (Provides): A package might depend on an abstract capability rather than a concrete package (e.g., depending on virtual-mta which can be satisfied by postfix, exim4, or sendmail).
  4. Co-Installability: Multiple versions of a shared library (e.g., libssl.so.1.1 and libssl.so.3) might be installable simultaneously if packaged under distinct names, but their binaries (/usr/bin/openssl) cannot overwrite each other.

Algorithmic Approaches

1. Depth-First Search (DFS) / Greedy Resolution

Used in early package managers and simple scripts. It recursively walks the dependency tree. If it encounters a conflict, it either halts with an error or attempts simple backtracking. - Limitation: Fails on complex graph topologies and cannot optimize for global criteria (such as minimizing total download size or preferring already installed versions).

2. Modern SAT Solvers (libsolv)

Modern package managers—such as Fedora’s dnf (via SUSE’s libsolv), openSUSE’s zypper, and Debian’s apt (via external solvers)—translate the entire repository and installed database into a Boolean formula in Conjunctive Normal Form (CNF):

  • Every package version is a boolean variable: \(P_{v} \in \{\text{True}, \text{False}\}\).
  • A dependency rule: “Installing \(A\) requires \(B \lor C\)” becomes the logical clause: \((\neg A \lor B \lor C)\).
  • A conflict rule: “A conflicts with \(D\)” becomes: \((\neg A \lor \neg D)\).
  • The user’s request: “Install \(A\)” adds the clause: \((A)\).

The solver then runs an optimized DPLL (Davis-Putnam-Logemann-Loveland) or CDCL (Conflict-Driven Clause Learning) algorithm to find a satisfying assignment for the entire formula. If no valid assignment exists, the solver backtracks and generates an exact, human-readable explanation of why the conflict cannot be resolved.