Я обнаружил, что пакет libmesa-devel требует (необоснованно)
libexpat-devel.  У пакета libmesa-devel прописано очень много
зависимостей вручную.

Такого быть не должно.  В иделе, все зависимости, прописанные
вручную, нужно удалить.  Чтобы это стало более возможным (и почти
возможным), нужно релизовать замыкание зависимостей по включаемым
хедерам.

Я также обнаружил, что 'сpp -M' и 'cpp -MM' плохо подохдят для задачи
вычисления зависимостей хедеров.  Но идея вычисления зависимостей
хедеров представляется не совсем уж утопической.

Можно использовать просто 'cpp'.
info cpp 'Preprocessor Output'

Вывод препроцессора позволяет построить стек включаемых файлов и,
следовательно, определить top-level includes.  Если первый флаг 1,
то это push на стек, а если первый флаг 2 -- то это pop.  Push на
начальной глубине даёт непосредственные зависимости исследуемого хедера.

$ cpp /usr/include/rpm/rpmlib.h |grep ^# |awk '$4==1{++I;if(I==1)print$3}$4==2{--I}'
"/usr/include/rpm/rpmio.h"
"/usr/include/rpm/rpmmessages.h"
"/usr/include/rpm/rpmerr.h"
"/usr/include/rpm/header.h"
"/usr/include/popt.h"
$ grep -w include /usr/include/rpm/rpmlib.h
#include "rpmio.h"
#include "rpmmessages.h"
#include "rpmerr.h"
#include "header.h"
#include "popt.h"
$