Résumé | Un réseau d'interactions peut être représenté par un graphe coloré. Une grande partie de la littérature est dédiée à la recherche de motifs dans ces graphes, avec une topologie donnée sur le motif (chemin, arbre, graphe...). Récemment, Lacroix et al. ont établi un nouveau problème où le motif n'a pas de topologie mais est simplement un (multi) ensemble de couleurs. On cherche alors un sous-graphe connexe contenant ce motif. Je présenterai différents résultats algorithmiques (complexité paramétrée, approximation) sur ce problème. |