Directed Feedback Vertex Set problem (Projet Algo des graphes L3 MIAGE 2026-2027)

En quelques mots:

Le but de ce projet est de participer à la track heuristic du challenge PACE pour le problème de graphe Directed Feedback Vertex Set* (DFVS) en proposant un ou plusieurs algorithmes pour le résoudre.

Dates

Directed Feedback Vertex Set

Étant donné un graphe orienté, une question basique consiste à déterminer quels sommets supprimer du graphe afin qu’il ne reste plus aucun cycle orienté dans le graphe. Voir Wikipedia.

Dans cet exemple, le graphe de gauche contient 2 cycles. Supprimer le sommet rouge supprimer tous les cycles du graphe.

Ce projet consiste à résoudre ce problème, dans le cadre d’un challenge international.

Ce problème est dit difficile à résoudre optimalement avec une complexité polynomiale (NP-difficile). Nous verrons donc des heuristiques, donnant une solution sans garantie d’optimalité mais de bonne qualité en pratique.

Une manière (bête) pour faire cela de manière non optimale consiste à supprimer tous les sommets du graphe : il n’y a évidemment plus aucun cycle dans le graphe. Une autre possibilité, moins radicale, consiste à ajouter des sommets dans une liste tant que leur ajout (dans le sous-graphe induit par cette liste) ne crée pas un cycle et de supprimer tous les autres sommets à la fin.

Évidemment, ces heuristiques ne permettent pas de trouver le nombre optimum (minimum) de sommets à supprimer pour résoudre le problème.

Le but de ce projet est de proposer et d’implémenter un (ou plusieurs) algorithme heuristique non trivial (originaux et efficaces) proposant une solution réalisable pour ce problème. C’est-à-dire qu’il n’est pas demandé d’avoir une solution forcément optimale, mais une solution valide : votre algorithme doit forcément produire un graphe sans cycle une fois que tous les sommets déterminés par l’algorithme sont supprimés. On souhaite toutefois avoir la solution la plus petite possible, ce qui donnera un classement.

Plus de détails

En effet, votre programme devra résoudre 100 instances différentes de ce problème, avec un temps maximum de 10 minutes par instance. La qualité de la solution pour chacune de ces instances apportera un score entre 0 et 1, et ainsi votre programme aura un score entre 0 et 100 au global. En plus de la plateforme optil.io (voir plus loin), je lancerai de temps en temps un script testant vos projets (automatiquement depuis github) dont la sortie se trouvera ici. La méthode de score sera celle décrite dans la section “scoring” de cette page (en gros, pour chaque instance, aucun point si trop loin de la solution optimum, 1 point si la solution optimum, et améliorer une bonne solution rapporte plus que d’améliorer une solution mauvaise).

Vous êtes encouragés à être créatifs dans vos heuristiques, à comparer plusieurs idées, et même à échouer sur certaines pistes, tant que vous les documentez dans votre rapport.

Ce qui est attendu

Obligatoirement

Une exécution typique de votre programme pourra être (avec les entrées et sorties standards):

cat file1.gr | python3 programme.py > solution

ou encore

python3 programme.py < file1.gr > solution

Pour tester le principe du signal, on peut faire ceci, ce qui envoie un signal SIGTERM après 10 secondes:

timeout 10s python3 programme.py < file1.gr > solution

Vous êtes libres de faire des programmes en plus pour tester différentes propriétés des instances, ou de faire des scripts testant automatiquement votre programme sur l’ensemble des instances (un exemple est donné sur le GIT).

Optionnellement

Attention, certains graphes sont très (très) grands, faites attention à la complexité, faites des approximations.

Il semble qu’une bonne approche consiste à :

Rendu

L’utilisation du GIT de github classroom est imposée. S’inscrire ici. Tous vos dépôts seront automatiquement clonés au moment de la deadline et la note se basera sur cet état. Il ne servira donc à rien de continuer à modifier votre code après la deadline.

Le projet est à faire seul.

Utilisez exclusivement le canal Teams pour toute question relative au projet.

Il est attendu sur votre Git :

LLM, plagiat…

Vous avez le droit de discuter entre vous et de lire des articles, mais vous devez préciser ce qui n’est pas de vous. Les idées ou le code provenant d’autres personnes ou de LLMs devront être mentionnées, dans les commentaires ou dans le rapport. Votre rapport contiendra, si vous êtes concernés, un retour critique et honnête sur votre utilisation d’IAs génératives. Vous pourrez indiquer les différents types de prompts utilisés (par ex. avec des liens vers les historiques de conversations), les retours critiques que vous avez eus sur le code ou algorithmes généré, les avantages et les inconvénients que vous avez identifiés sur l’utilisation de ce type d’outils. Vous devez être capable d’expliquer et justifier tout votre code, avec clarté et précision ! Le but est que vous appreniez des choses autour des graphes et de ses algorithmes.

Un détecteur de plagiat de code entre les soumissions de la classe sera utilisé.

La note finale prendra en compte largement votre score dans le challenge, mais aussi votre inventivité, la correction du programme, les expérimentations et analyses effectuées ainsi que votre capacité à expliquer vos choix et votre code.

Bon courage !