De la difficulté de trouver des chemins dissimilaires

Ali Al Zoobi (1) , David Coudert (1) , Nicolas Nisse (1)

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications

Lorsque l'on demande à son GPS un chemin pour aller à La Rochelle, celui-ci propose généralement plusieurs chemins assez différents les uns des autres : l'un par l'autoroute, l'autre par la côte, un pas cher, etc. La notion de (dis)similarité entre deux chemins a été définie, dans la littérature, de différentes manières qui toutes sont liées à un ratio entre la longueur de leur intersection et une certaine fonction de leurs longueurs. Nous étudions la complexité de plusieurs variantes du problème du calcul de chemins "dissimilaires" (dont la mesure de similarité n'excède pas un certain seuil) entre deux sommets d'un graphe orienté et pondéré. Pour quatre des mesures les plus étudiées dans la littérature, nous donnons une preuve unifiée et simple du fait que trouver $k$ plus courts chemins dissimilaires est NP-complet. En pratique, ce que l'on cherche est une alternative à un ou des chemins que l'on connait a priori. Nos résultats principaux concernent ce type de problème. Plus précisément, pour chacune des quatre mesures considérées, nous montrons que si $k\geq 2 $chemins sont donnés, en trouver un nouveau qui soit dissimilaire des premiers est NP-complet. Enfin, nous montrons que si un chemin $P$ est donné, trouver un plus court chemin parmi ceux qui sont dissimilaires de $P$ est NP-complet. Ce dernier résultat est à mettre en contraste avec le fait que, pour l'une des mesures, trouver un chemin dissimilaire à un chemin donné peut être résolu très simplement en temps polynomial.

Mots clés: Similarité entre chemins; $k$ plus courts chemins simples

Domaines: Complexité [cs.CC]

Ali Al Zoobi, David Coudert, Nicolas Nisse. De la difficulté de trouver des chemins dissimilaires. ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2021, La Rochelle, France. ⟨hal-03219987v2⟩