This was fixed in yakkety. The fix is also in 1.2.15 in xenial-proposed. But as that one is already uploaded, I'm not going to add an extra xenial task to this bug.
** Changed in: apt (Ubuntu) Status: Confirmed => Fix Released -- You received this bug notification because you are a member of Ubuntu Touch seeded packages, which is subscribed to apt in Ubuntu. https://bugs.launchpad.net/bugs/1472351 Title: autoremove keeps *all* providers of virtual rdeps unconditionally Status in apt package in Ubuntu: Fix Released Bug description: Hi, i'm using Ubuntu 14.04 LTS and I have an issue with autoremove command. The point is that I have Virtualbox package installed that has following tag: Recommends: linux-headers As a result autoremove marks all of linux-headers-*/linux-headers-*-generic packages as required and declines to sweep them. Please check the attached log file. To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/apt/+bug/1472351/+subscriptions -- Mailing list: https://launchpad.net/~touch-packages Post to : touch-packages@lists.launchpad.net Unsubscribe : https://launchpad.net/~touch-packages More help : https://help.launchpad.net/ListHelp