Keep only essential packages

With the following command you can obtain a list of installed packages, classified by priority:

dpkg-query -Wf '${Package;-40}${Priority}\n' | sort -b -k2,2 -k1,1

A description of priorities is given in the Debian Policy Manual.

In my installation I obtain the following (I only show required, important and standard packages):

apt                                     important
aptitude                                important
apt-utils                               important
bsdmainutils                            important
cron                                    important
debconf-i18n                            important
dmidecode                               important
gnupg                                   important
gpgv                                    important
groff-base                              important
info                                    important
install-info                            important
iptables                                important
iputils-ping                            important
isc-dhcp-client                         important
isc-dhcp-common                         important
libapt-inst1.3                          important
libapt-pkg4.11                          important
libboost-iostreams1.46.1                important
libcwidget3                             important
libept1                                 important
libgdbm3                                important
libgdbm3                                important
libgudev-1.0-0                          important
libnewt0.52                             important
libpcre3                                important
libpipeline1                            important
libpopt0                                important
libreadline6                            important
libssl1.0.0                             important
libsysfs2                               important
libusb-0.1-4                            important
libxapian22                             important
logrotate                               important
man-db                                  important
manpages                                important
medibuntu-keyring                       important
nano                                    important
netbase                                 important
net-tools                               important
python                                  important
readline-common                         important
rsyslog                                 important
ubuntu-extras-keyring                   important
ubuntu-keyring                          important
vim-common                              important
vim-tiny                                important
wget                                    important
whiptail                                important
adduser                                 required
base-files                              required
base-passwd                             required
bash                                    required
bsdutils                                required
busybox-initramfs                       required
coreutils                               required
cpio                                    required
dash                                    required
debconf                                 required
debianutils                             required
diffutils                               required
dpkg                                    required
e2fslibs                                required
e2fsprogs                               required
findutils                               required
gcc-4.6-base                            required
gcc-4.6-base                            required
grep                                    required
gzip                                    required
hostname                                required
ifupdown                                required
initscripts                             required
insserv                                 required
iproute                                 required
klibc-utils                             required
libacl1                                 required
libacl1                                 required
libattr1                                required
libattr1                                required
libblkid1                               required
libbz2-1.0                              required
libc6                                   required
libc6                                   required
libc-bin                                required
libcomerr2                              required
libcomerr2                              required
libdb5.1                                required
libdbus-1-3                             required
libdevmapper1.02.1                      required
libdrm2                                 required
libdrm-intel1                           required
libdrm-nouveau1a                        required
libdrm-radeon1                          required
libffi6                                 required
libgcc1                                 required
libgcc1                                 required
libglib2.0-0                            required
libklibc                                required
liblocale-gettext-perl                  required
liblzma2                                required
libmount1                               required
libncurses5                             required
libncursesw5                            required
libnih1                                 required
libnih-dbus1                            required
libpam0g                                required
libpam-modules                          required
libpam-modules-bin                      required
libpam-runtime                          required
libpciaccess0                           required
libpcre3                                required
libplymouth2                            required
libpng12-0                              required
libselinux1                             required
libselinux1                             required
libslang2                               required
libss2                                  required
libssl1.0.0                             required
libstdc++6                              required
libstdc++6                              required
libtext-charwidth-perl                  required
libtext-iconv-perl                      required
libtext-wrapi18n-perl                   required
libtinfo5                               required
libudev0                                required
libuuid1                                required
libuuid1                                required
locales                                 required
login                                   required
lsb-base                                required
lzma                                    required
makedev                                 required
mawk                                    required
module-init-tools                       required
mount                                   required
mountall                                required
multiarch-support                       required
ncurses-base                            required
ncurses-bin                             required
passwd                                  required
perl-base                               required
plymouth                                required
procps                                  required
python2.7-minimal                       required
python-minimal                          required
sed                                     required
sensible-utils                          required
sysvinit-utils                          required
sysv-rc                                 required
tar                                     required
tzdata                                  required
udev                                    required
upstart                                 required
ureadahead                              required
util-linux                              required
xz-utils                                required
zlib1g                                  required
zlib1g                                  required
at                                      standard
bash-completion                         standard
bc                                      standard
bind9-host                              standard
dc                                      standard
dnsutils                                standard
file                                    standard
ftp                                     standard
gettext-base                            standard
less                                    standard
libbind9-60                             standard
libcap2                                 standard
libdb5.1                                standard
libdns69                                standard
libedit2                                standard
libevent-2.0-5                          standard
libgc1c2                                standard
libgcrypt11                             standard
libgcrypt11                             standard
libgnutls26                             standard
libgnutls26                             standard
libgpg-error0                           standard
libgpg-error0                           standard
libgpm2                                 standard
libgssapi-krb5-2                        standard
libgssapi-krb5-2                        standard
libidn11                                standard
libidn11                                standard
libisc62                                standard
libk5crypto3                            standard
libk5crypto3                            standard
libkeyutils1                            standard
libkeyutils1                            standard
libkrb5-3                               standard
libkrb5-3                               standard
libkrb5support0                         standard
libkrb5support0                         standard
libldap-2.4-2                           standard
libldap-2.4-2                           standard
liblockfile1                            standard
liblwres60                              standard
libmagic1                               standard
libpci3                                 standard
libsasl2-2                              standard
libsasl2-2                              standard
libsqlite3-0                            standard
libsqlite3-0                            standard
libtasn1-3                              standard
libtasn1-3                              standard
libxml2                                 standard
lsof                                    standard
m4                                      standard
make                                    standard
mime-support                            standard
mlocate                                 standard
openssh-client                          standard
patch                                   standard
pciutils                                standard
perl                                    standard
perl-modules                            standard
python-apt                              standard
python-central                          standard
telnet                                  standard
time                                    standard
ucf                                     standard
wamerican                               standard
whois                                   standard

The Base System is defined as a system containing only required and important packages.

Packages marked as standard are not strictly needed for a working system, but you can get into difficulties if you miss them.

So, to remove all unneeded packages (optional and extra), you can execute the following command:

sudo apt-get --simulate purge $(dpkg-query -Wf '${Package;-40}${Priority}\n' | 
    awk '$2 ~ /optional|extra/ { print $1 }')

I added the --simulate option to be safe and see what apt says.

Strangely, it asks to remove also some required packages: e2fsprogs, util-linux, hostname and upstart, so it is necessary to reinstall these packages. I would download the packages in advance (apt-get download <packages>), to avoid network problems after.

Take also into account that for a working Wifi you can need some optional or extra package, removed in the above procedure.


Update 2019-02-26

In practice on a bunch of ubuntu VPS from different providers...I have found the original approach (below) to be quite brittle. On some systems they won't reboot because the below method will remove the kernel on KVM type virtualization (whereas openvz it mostly works). Instead of just patching the hack below everytime it breaks, I looked for an alternative way.

A seemingly (so far) better approach is the following:

# just in case we are retrying and apt is in a bad state
dpkg --configure -a

# DEBIAN_FRONTEND=noninteractive is useful for scripting. 
# prevents getting prompts that will hang our script.

# ubuntu-minimal is a meta package that depends on the packages 
# in ubuntu-minimal install.
# Need aptitude to autoremove everything we don't depend on.
DEBIAN_FRONTEND=noninteractive \
  apt-get --assume-yes install aptitude ubuntu-minimal

# mark all packages as automatically installed except
# ubuntu-minimal, kernel, systemd and openssh.
# For some reason systemd isn't part of ubuntu-minimal.
# Any dependencies of these four packages will be kept.
# All others that aren't dependencies will be removed since
# we have told apt they are automatically installed 
# (ie we don't care about them unless we need them as a dep)
DEBIAN_FRONTEND=noninteractive \
  aptitude --assume-yes markauto \
    '~i!?name(ubuntu-minimal~|linux-generic~|systemd~|openssh-server)'

# purge all removed packages that were not purged.
# removes leftover config/cruft.
DEBIAN_FRONTEND=noninteractive \
  aptitude --assume-yes purge '~c'

So far this works quite well in my testing on both openvz and kvm type virtualization. I use this as a first "bootstrapping" step to minimize the image before running my configuration management to setup the VPS the way I want it. I usually do a reboot after this step and before config management just to make sure we didn't break anything.

I am not doing apt clean or autoclean because my configuration management will be installing packages and so I would have to run apt-get update again anyway. If you are trying to build a minimal image in terms of disk space, then of course there is more you can do.

One more tip in case you lose DNS resolution after minimization... on Ubuntu 16.04, installing ubuntu-minimal installed resolvconf which wasn't installed before for some reason. This package (post-install) will make sure /etc/resolv.conf is setup to be dynamically built and that includes converting it into a symlink. If your VPS has static networking configuration (ie interfaces/IPs statically configured in /etc/network/interfaces and DNS statically configured in /etc/resolv.conf) then this will break your dns resolution. ie you will be able to ping 8.8.8.8 but not google.com (unknown host). I have a couple vps providers that provision the VPS this way instead of providing IP/DNS over dhcp. To work around this, I added a check before the above minimization like so:

if [ ! -L "/etc/resolv.conf" ]; then
  mkdir -p /etc/resolvconf/resolv.conf.d/
  cp /etc/resolv.conf /etc/resolvconf/resolv.conf.d/tail
fi

Basically: If the current /etc/resolv.conf is not a symlink, then assume we have a static configuration from our VPS provider. Copy the file to a special "tail" file for resolvconf. The "tail" file is a special file that resolvconf will append to the /etc/resolv.conf that it builds. This ensures you don't lose the static DNS configuration that was built into your VPS.

Original Answer

Following on @enzotib's answer...

Strange that required/important/essential packages would have optional/extra dependencies. Would think that if those are hard dependencies (as opposed to recommends or suggests) that those dependencies would also be set to the highest priority of the packages that depend on them.

On Ubuntu 16.04 I had a lot of important packages (apt, sudo, passwd, adduser) come up in the remove list when trying @enzotib's approach. As a dirty hack purged the list of optional/extra packages one by one with a script to see which optional/extra package purges were triggering removing required or important packages.

For example: in my case, purging optional package libaudit1 would wipe out a lot of important stuff.

root@ro01:~# apt-get purge libaudit1
Reading package lists...
Building dependency tree...
Reading state information...
The following additional packages will be installed:
  anacron bind9-host build-essential cpp cpp-5 dpkg-dev fakeroot g++ g++-5 gcc
  gcc-5 gcc-5-base initramfs-tools-bin libalgorithm-diff-perl
  libalgorithm-diff-xs-perl libalgorithm-merge-perl libapt-pkg5.0 libasan2
  libatomic1 libbind9-140 libc-dev-bin libc6 libc6-dev libcc1-0 libcilkrts5
  libdns162 libdpkg-perl libfakeroot libfile-fcntllock-perl libgcc-5-dev
  libgomp1 libisc160 libisccc140 libisccfg140 libisl15 libitm1 liblsan0
  liblwres141 libmpc3 libmpx0 libquadmath0 libstdc++-5-dev libstdc++6 libtsan0
  libubsan0 libudev1 linux-libc-dev logrotate manpages-dev samba-common
Suggested packages:
  default-mta | mail-transport-agent powermgmt-base cpp-doc gcc-5-locales
  debian-keyring g++-multilib g++-5-multilib gcc-5-doc libstdc++6-5-dbg
  gcc-multilib autoconf automake libtool flex bison gdb gcc-doc gcc-5-multilib
  libgcc1-dbg libgomp1-dbg libitm1-dbg libatomic1-dbg libasan2-dbg
  liblsan0-dbg libtsan0-dbg libubsan0-dbg libcilkrts5-dbg libmpx0-dbg
  libquadmath0-dbg glibc-doc libstdc++-5-doc mailx
Recommended packages:
  cron | cron-daemon rsyslog | system-log-daemon apt samba-common-bin
The following packages will be REMOVED:
  adduser* apache2* apache2-bin* apache2-utils* apt* apt-utils* aptitude*
  bind9* bsd-mailx* cron* dbus* dmsetup* fetchmail* ifupdown* initramfs-tools*
  initramfs-tools-core* initscripts* libapr1* libaprutil1*
  libaprutil1-dbd-sqlite3* libaprutil1-ldap* libaudit1* libblkid1*
  libcryptsetup4* libfdisk1* libmount1* libpam-modules* libpam-modules-bin*
  libpam-runtime* libpam0g* libsemanage1* libuuid1* libxapian22v5* login*
  mlocate* mount* mountall* openssh-client* openssh-server*
  openssh-sftp-server* passwd* plymouth* postfix* procps* python-samba*
  rpcbind* rsyslog* samba* samba-common-bin* samba-libs* sasl2-bin* screen*
  ssl-cert* sudo* systemd* systemd-sysv* udev* util-linux* uuid-runtime* wget*
The following NEW packages will be installed:
  anacron build-essential cpp cpp-5 dpkg-dev fakeroot g++ g++-5 gcc gcc-5
  libalgorithm-diff-perl libalgorithm-diff-xs-perl libalgorithm-merge-perl
  libasan2 libatomic1 libc-dev-bin libc6-dev libcc1-0 libcilkrts5 libdpkg-perl
  libfakeroot libfile-fcntllock-perl libgcc-5-dev libisl15 libitm1 liblsan0
  libmpc3 libmpx0 libquadmath0 libstdc++-5-dev libtsan0 libubsan0
  linux-libc-dev manpages-dev
The following packages will be upgraded:
  bind9-host gcc-5-base initramfs-tools-bin libapt-pkg5.0 libbind9-140 libc6
  libdns162 libgomp1 libisc160 libisccc140 libisccfg140 liblwres141 libstdc++6
  libudev1 logrotate samba-common
WARNING: The following essential packages will be removed.
This should NOT be done unless you know exactly what you are doing!
  apt adduser (due to apt) login libaudit1 (due to login)
  libpam0g (due to login) libpam-runtime (due to login)
  libpam-modules (due to login) mount libblkid1 (due to mount)
  libmount1 (due to mount) util-linux libfdisk1 (due to util-linux)
  libuuid1 (due to util-linux)
16 upgraded, 34 newly installed, 60 to remove and 124 not upgraded.
Need to get 41.1 MB of archives.
After this operation, 12.4 MB of additional disk space will be used.
You are about to do something potentially harmful.
To continue type in the phrase 'Yes, do as I say!'
 ?] Abort.

Also interesting that aptitude why and apt-cache rdepends show such different results.

root@ro01:~# dpkg-query -Wf '${Package;-40}${Priority}\n' | sort -b -k2,2 -k1,1 | grep 'libaudit1'
libaudit1                               optional

root@ro01:~# aptitude why libaudit1
i   sudo Depends libaudit1 (>= 1:2.2.1)

root@ro01:~# dpkg-query -Wf '${Package;-40}${Priority}\n' | sort -b -k2,2 -k1,1 | grep 'sudo '
sudo                                    optional

root@ro01:~# aptitude why sudo
i   mountall                   Depends    plymouth
p   plymouth                   Recommends plymouth-theme-ubuntu-text | plymouth-theme
p   mythbuntu-default-settings Provides   plymouth-theme
p   mythbuntu-default-settings Recommends lightdm
p   lightdm                    Recommends xserver-xorg
p   xserver-xorg               Recommends xserver-xorg-video-all | xorg-driver-video
p   nvidia-384                 Provides   xorg-driver-video
p   nvidia-384                 Depends    dkms
p   dkms                       Recommends menu | sudo

apt-cache rdepends shows a lot more...

root@ro01:~# apt-cache rdepends libaudit1
libaudit1
Reverse Depends:
  sudo
  systemd
  openssh-server
  libaudit-dev
  xwayland-hwe-16.04
  xserver-xephyr-hwe-16.04
  xmir-hwe-16.04
  sudo-ldap
  xserver-xorg-core-hwe-16.04
  systemd
  sudo
  libvirt0
  dbus-1-dbg
  dbus
  xwayland-hwe-16.04
  xwayland
  xvfb
  xserver-xephyr-hwe-16.04
  xserver-xephyr
  xnest
  xmir-hwe-16.04
  xmir
  xdmx
  sudo-ldap
  python3-audit
  python-audit
  nscd
  linux-oem-tools-4.13.0-1024
  linux-oem-tools-4.13.0-1022
  linux-oem-tools-4.13.0-1021
  linux-oem-tools-4.13.0-1020
  linux-oem-tools-4.13.0-1019
  linux-oem-tools-4.13.0-1017
  linux-oem-tools-4.13.0-1015
  linux-oem-tools-4.13.0-1012
  linux-oem-tools-4.13.0-1010
  linux-oem-tools-4.13.0-1008
  linux-kvm-tools-4.4.0-1004
  linux-gke-tools-4.4.0-1034
  linux-gke-tools-4.4.0-1033
  linux-gke-tools-4.4.0-1032
  linux-gke-tools-4.4.0-1031
  linux-gke-tools-4.4.0-1028
  linux-gke-tools-4.4.0-1027
  linux-gke-tools-4.4.0-1026
  linux-gke-tools-4.4.0-1024
  linux-gke-tools-4.4.0-1022
  linux-gke-tools-4.4.0-1018
  linux-gke-tools-4.4.0-1016
  linux-gke-tools-4.4.0-1014
  linux-gke-tools-4.4.0-1013
  linux-gke-tools-4.4.0-1012
  linux-gke-tools-4.4.0-1010
  linux-gke-tools-4.4.0-1009
  linux-gke-tools-4.4.0-1008
  linux-gke-tools-4.4.0-1006
  linux-gke-tools-4.4.0-1005
  linux-gke-tools-4.4.0-1003
  linux-gcp-tools-4.13.0-1013
  linux-gcp-tools-4.13.0-1012
  linux-gcp-tools-4.13.0-1011
  linux-gcp-tools-4.13.0-1008
  linux-gcp-tools-4.13.0-1007
  linux-gcp-tools-4.13.0-1006
  linux-gcp-tools-4.13.0-1002
  linux-gcp-tools-4.10.0-1009
  linux-gcp-tools-4.10.0-1008
  linux-gcp-tools-4.10.0-1007
  linux-gcp-tools-4.10.0-1006
  linux-gcp-tools-4.10.0-1004
  linux-euclid-tools-4.4.0-9026
  linux-euclid-tools-4.4.0-9025
  linux-euclid-tools-4.4.0-9023
  linux-euclid-tools-4.4.0-9022
  linux-euclid-tools-4.4.0-9021
  linux-euclid-tools-4.4.0-9020
  linux-euclid-tools-4.4.0-9019
  linux-azure-edge-tools-4.15.0-1005
  linux-azure-edge-tools-4.14.0-1003
  linux-azure-edge-tools-4.13.0-1005
  linux-azure-edge-tools-4.13.0-1003
  linux-aws-tools-4.4.0-1012
  linux-aws-tools-4.4.0-1011
  linux-aws-tools-4.4.0-1009
  linux-aws-tools-4.4.0-1007
  linux-aws-tools-4.4.0-1004
  linux-aws-tools-4.4.0-1003
  linux-aws-tools-4.4.0-1001
  gdm3
  xserver-xorg-core-hwe-16.04
  xserver-xorg-core
  util-linux
  systemd
  sudo
  passwd
  openssh-server
  login
  linux-tools-4.4.0-98
  linux-tools-4.4.0-97
  linux-tools-4.4.0-96
  linux-tools-4.4.0-93
  linux-tools-4.4.0-92
  linux-tools-4.4.0-91
  linux-tools-4.4.0-89
  linux-tools-4.4.0-87
  linux-tools-4.4.0-83
  linux-tools-4.4.0-81
  linux-tools-4.4.0-79
  linux-tools-4.4.0-78
  linux-tools-4.4.0-77
  linux-tools-4.4.0-75
  linux-tools-4.4.0-72
  linux-tools-4.4.0-71
  linux-tools-4.4.0-70
  linux-tools-4.4.0-67
  linux-tools-4.4.0-66
  linux-tools-4.4.0-64
  linux-tools-4.4.0-63
  linux-tools-4.4.0-62
  linux-tools-4.4.0-59
  linux-tools-4.4.0-57
  linux-tools-4.4.0-53
  linux-tools-4.4.0-51
  linux-tools-4.4.0-47
  linux-tools-4.4.0-45
  linux-tools-4.4.0-43
  linux-tools-4.4.0-42
  linux-tools-4.4.0-38
  linux-tools-4.4.0-36
  linux-tools-4.4.0-34
  linux-tools-4.4.0-31
  linux-tools-4.4.0-28
  linux-tools-4.4.0-24
  linux-tools-4.4.0-22
  linux-tools-4.4.0-122
  linux-tools-4.4.0-121
  linux-tools-4.4.0-119
  linux-tools-4.4.0-116
  linux-tools-4.4.0-112
  linux-tools-4.4.0-109
  linux-tools-4.4.0-108
  linux-tools-4.4.0-104
  linux-tools-4.4.0-103
  linux-tools-4.4.0-101
  linux-kvm-tools-4.4.0-1021
  linux-kvm-tools-4.4.0-1020
  linux-kvm-tools-4.4.0-1019
  linux-kvm-tools-4.4.0-1017
  linux-kvm-tools-4.4.0-1015
  linux-kvm-tools-4.4.0-1013
  linux-kvm-tools-4.4.0-1012
  linux-kvm-tools-4.4.0-1010
  linux-kvm-tools-4.4.0-1009
  linux-kvm-tools-4.4.0-1008
  linux-kvm-tools-4.4.0-1007
  linux-hwe-tools-4.8.0-58
  linux-hwe-tools-4.8.0-56
  linux-hwe-tools-4.8.0-54
  linux-hwe-tools-4.8.0-53
  linux-hwe-tools-4.8.0-52
  linux-hwe-tools-4.8.0-51
  linux-hwe-tools-4.8.0-49
  linux-hwe-tools-4.8.0-46
  linux-hwe-tools-4.8.0-45
  linux-hwe-tools-4.8.0-44
  linux-hwe-tools-4.8.0-42
  linux-hwe-tools-4.8.0-41
  linux-hwe-tools-4.8.0-39
  linux-hwe-tools-4.8.0-36
  linux-hwe-tools-4.13.0-39
  linux-hwe-tools-4.13.0-38
  linux-hwe-tools-4.13.0-37
  linux-hwe-tools-4.13.0-36
  linux-hwe-tools-4.13.0-32
  linux-hwe-tools-4.13.0-31
  linux-hwe-tools-4.13.0-26
  linux-hwe-tools-4.10.0-42
  linux-hwe-tools-4.10.0-40
  linux-hwe-tools-4.10.0-38
  linux-hwe-tools-4.10.0-37
  linux-hwe-tools-4.10.0-35
  linux-hwe-tools-4.10.0-33
  linux-hwe-tools-4.10.0-32
  linux-hwe-tools-4.10.0-30
  linux-hwe-tools-4.10.0-28
  linux-hwe-tools-4.10.0-27
  linux-hwe-edge-tools-4.8.0-34
  linux-hwe-edge-tools-4.15.0-15
  linux-hwe-edge-tools-4.15.0-13
  linux-hwe-edge-tools-4.13.0-25
  linux-hwe-edge-tools-4.13.0-21
  linux-hwe-edge-tools-4.13.0-19
  linux-hwe-edge-tools-4.13.0-17
  linux-hwe-edge-tools-4.13.0-16
  linux-hwe-edge-tools-4.11.0-14
  linux-hwe-edge-tools-4.11.0-13
  linux-hwe-edge-tools-4.10.0-26
  linux-hwe-edge-tools-4.10.0-24
  linux-hwe-edge-tools-4.10.0-22
  linux-hwe-edge-tools-4.10.0-21
  linux-hwe-edge-tools-4.10.0-20
  linux-hwe-edge-tools-4.10.0-19
  linux-hwe-edge-tools-4.10.0-14
  linux-azure-tools-4.13.0-1014
  linux-azure-tools-4.13.0-1012
  linux-azure-tools-4.13.0-1011
  linux-azure-tools-4.13.0-1009
  linux-azure-tools-4.13.0-1007
  linux-azure-tools-4.13.0-1006
  linux-azure-tools-4.13.0-1005
  linux-azure-tools-4.11.0-1016
  linux-azure-tools-4.11.0-1015
  linux-azure-tools-4.11.0-1014
  linux-azure-tools-4.11.0-1013
  linux-azure-tools-4.11.0-1011
  linux-azure-tools-4.11.0-1009
  linux-aws-tools-4.4.0-1055
  linux-aws-tools-4.4.0-1054
  linux-aws-tools-4.4.0-1052
  linux-aws-tools-4.4.0-1050
  linux-aws-tools-4.4.0-1049
  linux-aws-tools-4.4.0-1048
  linux-aws-tools-4.4.0-1047
  linux-aws-tools-4.4.0-1044
  linux-aws-tools-4.4.0-1043
  linux-aws-tools-4.4.0-1041
  linux-aws-tools-4.4.0-1039
  linux-aws-tools-4.4.0-1038
  linux-aws-tools-4.4.0-1037
  linux-aws-tools-4.4.0-1035
  linux-aws-tools-4.4.0-1032
  linux-aws-tools-4.4.0-1031
  linux-aws-tools-4.4.0-1030
  linux-aws-tools-4.4.0-1028
  linux-aws-tools-4.4.0-1026
  linux-aws-tools-4.4.0-1022
  linux-aws-tools-4.4.0-1020
  linux-aws-tools-4.4.0-1018
  linux-aws-tools-4.4.0-1017
  linux-aws-tools-4.4.0-1016
  linux-aws-tools-4.4.0-1013
  libvirt0
  libpam0g
  libpam-modules-bin
  libpam-modules
  libauparse0
  libauparse0
  libauparse0
  libaudit-common
  libaudit-common
  libaudit-common
  dbus-1-dbg
  dbus
  auditd
  xwayland
  xvfb
  xserver-xephyr
  xnest
  xmir
  xdmx
  ubuntu-core-libs
  sudo-ldap
  python3-audit
  python-audit
  policycoreutils
  nscd
  gdm3
  aide-dynamic
  xserver-xorg-core
  systemd
  sudo
  passwd
  openssh-server
  login
  linux-tools-4.4.0-21
  libvirt0
  libsemanage1
  libpam0g
  libpam-modules-bin
  libpam-modules
  libauparse0
  libauparse0
  libauparse0
  libaudit-dev
  libaudit-common
  dbus
  dbus-1-dbg
  auditd
root@ro01:~#

Found some more problematic packages...

  • libdebconfclient0
  • liblz4-1
  • libsemanage1
  • libsemanage-common
  • libsystemd0
  • libbsd0
  • libexpat1
  • libhcrypto4-heimdal
  • libheimntlm0-heimdal
  • libhx509-5-heimdal

When running apt-get purge for packages one by one, I no longer got the warning about removing important packages and scanning through the list of stuff removed, I saw important stuff like adduser and apt were not longer being removed. However when running apt-get purge for all packages at once...the warning was still there and apt and other things were on the remove list again despite not being there when removing packages individually. No idea.

In the end, I just excluded all libraries and a few other packages in order to avoid removing anything I cared about.

root@ro01:~# apt-get purge $(dpkg-query -Wf \
    '${Package;-40}${Priority}\n' | \
    awk '$2 ~ /optional|extra/ { print $1 }' | \
    grep -vE 'lib|gawk|openssh|insserv|quota|sudo')
Reading package lists... Done
Building dependency tree... Done
The following packages will be REMOVED:
  apache2* apache2-bin* apache2-data* apache2-doc* apache2-utils* bind9* bind9utils* binutils* bsd-mailx* busybox-initramfs* ca-certificates* cifs-utils* console-data* db-util* db5.3-util* debconf-utils* dh-python*
  dialog* distro-info-data* dmsetup* dselect* ed* expat* fetchmail* finger* fontconfig* fontconfig-config* fonts-dejavu* fonts-dejavu-core* fonts-dejavu-extra* fonts-freefont-ttf* gettext* initramfs-tools*
  initramfs-tools-bin* initramfs-tools-core* iputils-arping* iputils-tracepath* ldap-utils* libfontconfig1* linux-base* lsb-release* lynx* lynx-common* make* makedev* memtester* mktemp* module-init-tools* mountall*
  mtools* odbcinst* odbcinst1debian2* openssl* openssl-blacklist* plymouth* postfix* procinfo* psmisc* psutils* pwgen* python-crypto* python-dnspython* python-ldb* python-samba* python-talloc* python-tdb* python3*
  python3-minimal* python3.5* python3.5-minimal* rsync* samba* samba-common* samba-common-bin* samba-libs* sasl2-bin* sharutils* snmp* ssl-cert* syslinux* tcpdump* tcsh* tdb-tools* tofrodos* ttf-dejavu* ttf-dejavu-core*
  ttf-dejavu-extra* ttf-freefont* unixodbc* unzip* update-inetd* uuid-runtime* vim* vim-runtime* wide-dhcpv6-client* xinetd*
0 upgraded, 0 newly installed, 96 to remove and 0 not upgraded.
After this operation, 195 MB disk space will be freed.
Do you want to continue? [Y/n] Y