What I am trying to achieve:
How to know - beyond blind trial&errro - what is the maximally possible set of packages to uninstall but still having a minimal working system?
This is easy for Debian and Ubuntu, which have the concept of essential packages. These are packages without which the system will not function and which are assumed to be on all systems; as such, no dependency on them is required.
Essential packages may depend on non-essential packages, since a shared library may not be essential. You'll therefore have to resolve the dependencies yourself, or just be sure you pull them in.
Note that you may not find a system with only essential packages very useful: it doesn't contain apt to install more packages from the Internet and it doesn't contain a kernel, since not all environments need a kernel. However, provided you can get software onto the system, you can install additional packages.
Red Hat and CentOS don't document which packages are required outside of a minimal install, so you'll have to just use trial and error there. You may find that the same set of packages as for Debian (minus Perl) may be a good starting point. You may also find this CentOS forum thread interesting.
Going from full system to minimal will be long and painful.
I suggest going the other way : Start from a minimal Linux distribution and add to it the additional packages that you need with their dependencies.
A list of tiny Linux distributions with reviews can be found in the article
The 8 Smallest Linux Distros That Are Lightweight and Need Almost No Space.
You will find there small distributions based on Debian and on Ubuntu. I have not been able to find one based on CentOS.
