Sparsification pour des problèmes d'optimisation sur des graphes et des matroïdes

La sparsification (que l’on pourrait traduire en français par "éparsification") fait référence au processus de réduction de la taille ou de la densité d’un objet combinatoire tout en préservant certaines propriétés. Par exemple, dans les algorithmes de graphes, la sparsification consiste à trouver un graphe plus petit et moins dense qui préserve approximativement certaines propriétés du graphe original, telles que la connectivité, les distances entre les sommets ou la taille du couplage maximum. Une telle sparsification réduit l’utilisation de la mémoire et accélère les calculs ; par conséquent, elle est particulièrement utile pour traiter des problèmes de grande taille. Dans cette thèse, nous montrons que certaines techniques de sparsification pour les problèmes de graphes peuvent être appliquées dans des contextes plus généraux, en mettant l’accent sur le problème de couplage maximum et le problème de couverture maximale sous contrainte par des sommets. Nous présentons quelques applications de ces techniques au streaming, à la complexité de communication et aux algorithmes à complexité paramétrée. Dans les premiers chapitres de cette thèse, nous exploitons certaines idées spécifiques aux graphes pour étendre des techniques existantes. Le premier exemple que nous donnons est celui d’un sparsifieur (ou "objet éparsifié") initialement développé pour le problème de couplage maximum, que nous étendons au problème de b-couplage pondéré. Ensuite, nous généralisons une construction de noyau, développée initialement pour le problème de couverture maximale sous contrainte de cardinalité, à la version de ce problème contrainte par un matroïde, pour certains matroïdes pouvant être représentés par un graphe simple. Les derniers chapitres de cette thèse traitent des matroïdes plus généraux et sont construits autour du concept de densité dans un matroïde. En particulier, sur la base de ce concept, nous adaptons le sparsifieur de couplage maximum mentionné précédemment pour traiter l’intersection de matroïdes, une généralisation du couplage biparti. Enfin, nous revenons au problème de couverture maximale contrainte par matroïde et proposons une technique de sparsification qui fonctionne pour tout type de matroïde.