Предложите лучший алгоритм.
Ну можно например что-то типа такого.
Выбираем все пакеты от которых зависит удаляемый пакет. Это "кандидаты на удаление". "Глубину" на которую отбираем "кандидатов" можно задать параметром.
Для каждого из них проверяем по зависимостям, существует ли хотя-бы один пакет, зависящий от "кандидата", но не попавший в список "кандидатов". Если такой пакет находится - то "кандидата" из списка вычеркиваем.
Все что осталось после прохода в списке - предъявляем пользователю для подтверждения удаления.
Вариант номер два - когда пользователь устанавливает какой-либо пакет он помечается где-то как "явно установленный". Все остальные, притянутые по зависимостям имеют статус "автоматически установленных". Соответственно, некий скрипт ищет "автоматически установленные" пакеты на которые нет зависимостей и предлагает их удалить.