How can I mark all packages with installed dependents as "Automatically Installed"?
You could use Aptitude's why
command:
for x in $(apt-mark showmanual)
do
r="$(echo ${x} | sed -e 's/\([+.]\)/[\1]/g')"
aptitude why ${x} | egrep -q "^i.* (Pre)?Depends +${r}( |$)" && apt-mark auto ${x}
done
Not tested, because it's not something I want to (have to un-)do on my machine.