Diverse Routing with Star SRLGs

International audienceLa notion de groupe de liens partageant un risque (Shared Risk Link Group, SRLG) a été introduite pour modéliser des problèmes de tolérance aux pannes simultanées d'ensembles de liens d'un réseau. Dans ce contexte, le problème du routage diversifié est de trouver un ensemble de chemins SRLG-disjoints entre une paire donnée de noeuds du réseau. Ce problème a été prouvé NP-complet en général et certains cas polynomiaux ont été caractérisés. Nous avons étudié le problème du routage diversifié dans les réseaux satisfaisant la propriété d'étoile. Dans un réseau satisfaisant la propriété d'étoile, un lien peut être affecté par plusieurs SRLGs, mais tous les liens affectés par un même SRLG sont incidents à un même sommet. Nous avons trouvé des contre-exemples à un algorithme polynomial publié pour le calcul de paires de chemins SRLG-disjoints dans les réseaux satisfaisants la propriété d'étoile. Puis, nous avons prouvé que ce problème est en fait NP-difficile. Plus généralement, nous avons montré que le problème du routage diversifié dans les réseaux avec la propriété d'étoile est NP-difficile, APX-difficile, et W[1]-difficile lorsque le paramètre est le nombre de chemins SRLG-disjoints. Enfin, nous avons caractérisé de nouvelles instances polynomiales, en particulier lorsque le degré maximum des sommets est 4, ou lorsque le réseau est acyclique