Abstract
All Pairs Shortest Path (APSP) is a classic problem in graph theory. While for general weighted graphs there is no algorithm that computes APSP in O(n^{3epsilon}) time (epsilon > 0), by using fast matrix multiplication algorithms, we can compute APSP in O(n^{omega}*log(n)) time (omega < 2.373) for undirected unweighted graphs, and in O(n^{2.5302}) time for directed unweighted graphs. In the current state of matters, there is a substantial gap between the upper bounds of the problem for undirected and directed graphs, and for a long time, it is remained an important open question whether it is possible to close this gap.
In this paper we introduce a new parameter that measures the symmetry of directed graphs (i.e. their closeness to undirected graphs), and obtain a new parameterized APSP algorithm for directed unweighted graphs, that generalizes Seidel's O(n^{omega}*log(n)) time algorithm for undirected unweighted graphs. Given a directed unweighted graph G, unless it is highly asymmetric, our algorithms can compute APSP in o(n^{2.5}) time for G, providing for such graphs a faster APSP algorithm than the stateoftheart algorithms for the problem.
BibTeX  Entry
@InProceedings{porat_et_al:LIPIcs:2016:6420,
author = {Ely Porat and Eduard Shahbazian and Roei Tov},
title = {{New Parameterized Algorithms for APSP in Directed Graphs}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {72:172:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6420},
URN = {urn:nbn:de:0030drops64207},
doi = {10.4230/LIPIcs.ESA.2016.72},
annote = {Keywords: Graphs, distances, APSP, fast matrix multiplication}
}
Keywords: 

Graphs, distances, APSP, fast matrix multiplication 
Collection: 

24th Annual European Symposium on Algorithms (ESA 2016) 
Issue Date: 

2016 
Date of publication: 

18.08.2016 