Le feu ça brûle et l'informatique ça bugge : combustion et régression dans les graphes

Dans cette thèse, nous étudions deux problèmes de graphe impliquant une formede propagation.Le premier problème consiste à retrouver une régression dans le dépôt d’un projetgéré par un logiciel de gestion de versions tel que Git. L’ensemble des versions du dépôtest représenté par un graphe orienté acyclique (DAG) où les sommets correspondentaux versions du projet et les arcs aux changements apportés entre différentes versions.On suppose qu’un bug a été introduit dans l’une des versions du projet et que celui-cise diffuse dans toutes les versions ultérieures à la version d’introduction. Il est possibled’effectuer une requête sur un sommet pour savoir si la version correspondantecontient le bug ou non. Étant donné un DAG et un sommet buggé, le Problème d’Identificationde Régression consiste à trouver le premier sommet contenant le bug et celaen un minimum de requêtes dans le pire cas. Ce problème est réputé NP-complet.On étudie l’algorithme provenant de Git, appelé git bisect, et répondant à ceproblème. On démontre dans le cas général que git bisect peut utiliser un nombre derequêtes exponentiellement plus élevé que celui d’un algorithmeoptimal.Onconsidèreégalement la restriction où tous les sommets ont un degré entrant d’au plus 2 (c.-à-d.des fusions de branches faites avec au plus deux branches à la fois). On démontre dansce cas que git bisect est un algorithme d’approximation. On propose également unmeilleur algorithme d’approximation pour ce cas ainsi qu’une preuve alternative dela NP-complétude du Problème d’Identification de Régression. On étudie égalementgit bisect sur une seconde restriction amenant des DAG plus proche de la réalitédes dépôts. Puis on propose une méthode de génération aléatoire de ces DAG afind’étudier le nombre de requêtes de git bisect dans le pire cas. Enfin on s’intéresse àune variante de l’algorithme git bisect qui ne réduit plus l’ensemble des sommetsrequêtables au cours de son exécution.Le second problème s’intéresse à la combustion de graphe qui consiste à brûlerl’ensemble des sommets d’un graphe le plus rapidement possible. Pour y parvenir dessommets du graphe sont choisis successivement pour être brûlés. Lorsqu’un sommetbrûle, le feu se propage à travers les arêtes connectées au sommet et brûle ainsi tous sonvoisinage. Une étape de combustion commence par la propagation du feu au voisinagedes sommets qui brûlent et finit par l’allumage d’un nouveau sommet. La combustionse termine une fois que tous les sommets du graphe sont brûlés. Le but est de brûlerl’ensemble des sommets du graphe en un nombre minimum d’étapes que l’on appellele nombre de combustion. Le problème de combustion de graphe étudié dans cettethèse est appelé Problème de Combustion Orienté Maximum. Étant donné un graphenon orienté, le problème consiste à trouver l’orientation du graphe qui rends la plusrapide des combustions sur ce graphe orienté plus longue que celles de toutes lesautres orientations du graphe, autrement dit, qui maximise le nombre de combustiondu graphe.Ondémontre tout d’abordque ce problème estNP-difficile sur les graphes connexes.Dans un second temps on montre l’existence de bornes pour le nombre de combustion(appelé nombre de combustion orienté maximum pour ce problème) et le lien avec lataille du stable maximum du graphe. On montre également qu’il existe sur les graphescomplets et les forêts une orientation telle que le nombre de combustion orienté maximumest plus petit ou égal au stable maximum du graphe. Enfin on propose unalgorithme polynomial pour la résolution du problème sur les forêts.