can you come up with an algorithm that solves the problem?

sub uninstall {
    my ($pkg) = @_;
    return if !installed($pkg);
    uninstall($_) for get_dependencies($pkg);
    ... uninstall $pkg here ...
}
[download]

Update: Ah, nevermind. That deletes dependencies that are still in use. Why would you want to do delete a dependency that's still in use? By that logic, uninstalling CGI::Simple should uninstall perl (strict's distribution).