Comment 2 for bug 122047

As a workaround, I've attached a script that outputs a list of all packages that are not auto-installed. Here is some sample output:

can_be_marked_as_auto acpi
can_be_marked_as_auto acpi-support
can_be_marked_as_auto acpid
can_be_marked_as_auto adduser
can_be_marked_as_auto alacarte
can_be_marked_as_auto alsa-base
can_be_marked_as_auto alsa-utils
can_be_marked_as_auto amarok-xine
can_be_marked_as_auto anacron
no_dependents apache2
can_be_marked_as_auto apmd
can_be_marked_as_auto app-install-data
no_dependents app-install-data-commercial
can_be_marked_as_auto apparmor
no_dependents apparmor-utils
can_be_marked_as_auto apport
no_dependents apport-gtk
no_dependents apt-rdepends
can_be_marked_as_auto aptitude
can_be_marked_as_auto apturl

The text "no_dependents" indicates that no packages depend on the listed package. These packages can (supposedly) be removed without affecting any other package.

The text "can_be_marked_as_auto" indicates that at least one other package depends on the listed package. These packages can be marked as being automatically installed (via Synaptic by going to Package..Automatically installed or via aptitude by pressing Shift-M).

The script is really slow because there is no fast and reliable way to get reverse dependencies for a package.