Don't depend on dpkg (>= 1.15.4) | install-info. The purpose of this dependency, pursuant to a "should" directive in policy, is to ensure that /usr/share/info/dir is properly rebuilt during upgrades. Unfortunately, this dependency introduces a loop on upgrades from Ubuntu 8.04 LTS that can't be broken without the use of --force-depends: libc6 Depends: findutils (>= 4.4.0-2ubuntu2) findutils Depends: dpkg (>= 1.15.4) | install-info dpkg Pre-Depends: libc6 (>= 2.11) Since it isn't the end of the world if the info directory isn't rebuilt when doing a partial upgrade of just findutils, this is the safest place to break that loop. We can drop this change after Ubuntu 10.04 LTS is released.