Average-case complexity of shortest-paths problems

Abstract

We study both upper and lower bounds on the average-case complexity of shortestpaths algorithms. It is proved that the all-pairs shortest-paths problem on n-vertex networks can be solved in time O(n^2 log n) with high probability with respect to various probability distributions on the set of inputs. Our results include the first theoretical analysis of the average behavior of shortest-paths algorithms with respect to the vertex-potential model, a family of probability distributions on complete networks with arbitrary real arc costs but without negative cycles. We also generalize earlier work with respect to the common uniform model, and we correct the analysis of an algorithm with respect to the endpoint-independent model. For the algorithm that solves the all-pairs shortest-paths problem on networks generated according to the vertex-potential model, a key ingredient is an algorithm that solves the single-source shortest-paths problem on such networks in time O(n^2) with high probability. All algorithms mentioned exploit that with high probability, the single-source shortest-paths problem can be solved correctly by considering only a rather sparse subset of the arc set. We prove a lower bound indicating the limitations of this approach. In a fairly general probabilistic model, any algorithm solving the single-source shortest-paths problem has to inspect OMEGA(n log n) arcs with high probability.

In dieser Arbeit werden sowohl obere als auch untere Schranken für die average-case-Komplexität von Kürzeste-Wege-Algorithmen untersucht. Wir beweisen für verschiedene Wahrscheinlichkeitsverteilungen auf Netzwerken mit n Knoten, dass das all-pairs shortest-paths problem mit hoher Wahrscheinlichkeit in Zeit O(n^2 log n) gelöst werden kann. Insbesondere können wir dieses Laufzeit für einen Algorithmus beweisen, dessen Eingaben gemäß des vertex-potential model erzeugt werden, einer Familie von Wahrscheinlichkeitsverteilungen auf vollständigen Netzwerke mit reellen Kantenkosten, die jedoch keine negative Kreise besitzen. Theoretische Ergebnisse für dieses Eingabemodell waren bislang nicht bekannt. Wir verallgemeinern außerdem frühere Arbeit bezüglich des uniform model und korrigieren die Laufzeit-Analyse eines Algorithmus bezüglich des endpoint-independent model. Der Algorithmus, der das all-pairs shortest-paths problem auf Netzwerken löst, die gemäß des vertex-potential model erzeugt werden, baut entscheidend darauf auf, dass wir auch einen Algorithmus entwickeln, der das single-source shortest-paths problem auf solchen Netzwerken mit hoher Wahrscheinlichkeit in Zeit O(n^2) löst. Alle bislang erwähnten Algorithmen nutzen aus, dass das single-source shortest-paths problem auch dann mit hoher Wahrscheinlichkeit korrekt gelöst werden kann, wenn wir nur einen Teil der Kantenmenge betrachten. Wir beweisen eine untere Schranke, die die Grenzen dieses Reduktionsansatzes belegt. Auf einer Klasse von Netzwerken mit ganzzahligen Kantenkosten muss jeder Algorithmus mit hoher Wahrscheinlichkeit OMEGA(n log n) Kanten inspizieren, um das single-source shortest-paths problem zu lösen.