We identify a new ``controlled'' version of the shortest paths
problem. By selecting exactly one outgoing edge in each of the
controlled vertices we want to make the shortest distances from all
vertices to the unique sink as long as possible. Under reasonable
assumptions the problem belongs to the complexity class
\textsc{NP}$\cap$\textsc{coNP}. Mean payoff games are easily reducible
to this problem. We suggest an algorithm for computing longest
shortest paths. Player Max selects a strategy (one edge in each
controlled vertex) and player Min responds by evaluating shortest
paths to the sink in the remaining graph. Then Max locally changes
choices in controlled vertices looking at attractive switches that
seem to increase shortest paths (under the current evaluation). We
show that this is a monotonic strategy improvement, and any locally
optimal strategy is globally optimal. This allows us to construct a
randomized algorithm of complexity
\[\min(poly\cdot W,\;2^{O(\sqrt{n\log n})}),\] which is simultaneously
pseudopolynomial ($W$ is the maximal absolute edge weight) and
subexponential in the number of vertices $n$. All previous algorithms
for mean payoff games were either exponential or pseudopolynomial
(which is purely exponential for exponentially large edge weights).
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-05.ps.gz
DIMACS Home Page