если отвечать на вопрос как он задан, то
aptitude remove mariadb-server mariadb-client
с настройками по умолчанию удалит те пакеты, на которые ругался apt-get, и автоматически установленные пакеты.
purge стоит делать только осознанно, он отличается от обычного remove тем, что удаляются все конфиги (если у вас стоит задача перейти на более новую версию, то это может быть не то, что вам нужно).
если же «читать между строк», то конечная цель — не удаление пакетов, а разрешение зависимостей.
можно попробовать использовать aptitude, у него немного другой алгоритм разрешения зависимостей + есть интерактивный режим.
просто запускаете aptitude, в нижней строке будет подсказка по горячим кнопкам.