AFAICT that's not always true. Several scripting languages allow circular dependencies (Node.js, Perl) and so do some popular package managers (with specific workarounds, but the point is that such dependency constellations exist): https://www.debian.org/doc/debian-policy/ch-relationships.ht...
Perhaps the problem needs to be examined differently depending on allowed/existing-in-the-wild circular dependencies.
> AFAICT that's not always true.
And you are right. apt-get has "upgrade" and "dist-upgrade" commands for a long, long time for a reason (the latter allows to upgrade packages in the presence of dependency cycles and some other cases that would be nasty if left in the middle of upgrade; obviously, no changes that need dist-upgrade land in Debian stable).
It seems that the problem then might not even have a solution in all cases. So perhaps we should rethink the problem.
If you allow side-by-side versions then the only remaining failure case is a dependency that doesn't exist.
Nothing to rethink there.
However, this is the killer:
"Two different versions of a package cannot be installed simultaneously."
Get rid of that, and your problems disappear.
Which is why my linux server has:
1 gcc-4.8-base:amd64
2 gcc-4.9-base:amd64
3 gcc-5-base:amd64
4 gcc-6-base:amd64