## Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

Abstract

We study dynamic $(1+\epsilon)$-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected $n$-node $m$-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of $\tilde O(mn)$ and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of $O(mn^2)$ and constant query time. We improve these results as follows:

(1) We present an algorithm with a total update time of $\tilde O(n^{5/2})$ and constant query time that has an additive error of two in addition to the $(1+\epsilon)$ multiplicative error. This beats the previous $\tilde O(mn)$ time when $m=\Omega(n^{3/2})$. Note that the additive error is unavoidable since, even in the  static case, an $O(n^{3-\delta})$-time (a so-called truly subcubic) combinatorial algorithm with $(1+\epsilon)$ multiplicative error cannot have an additive error less than $2-\epsilon$, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a $(2+\epsilon)$-approximation algorithm (without an additive error) with the same time guarantees, improving the recent $(3+\epsilon)$-approximation algorithm with $\tilde O(n^{5/2+O(1/\sqrt{\log n})})$ running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees.

(2) We present a deterministic algorithm with a total update time of $\tilde O(mn)$ and a query time of $O(\log\log n)$. The algorithm has a multiplicative error of $(1+\epsilon)$ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper.

In order to achieve our results, we introduce two new techniques: (1) A monotone Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator.  (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.

## Faster Algorithms for Semi-Matching Problems

Author Jittat Fakcharoenphol, Bundit Lekhanukit, Danupon Nanongkai

Conference: ICALP 2010

Abstract:

We consider the problem of finding semi-matching in bipartite graphs, a problem also extensively studied under various names in the scheduling literature. We give faster algorithms for both weighted and unweighted case.

For the weighted case, we give an $O(nm\log n)$-time algorithm, where $n$ is the number of vertices and $m$ is the number of edges, by exploiting geometric structure of the problem. This improves the classical $O(n^3)$ algorithms by Horn [Operations Research 1973] and Brono, Coffman and Sethi [Communications of the ACM 1974].

For the unweighted case, the bound could be improved even further. We give a simple divide-and-conquer algorithm which runs in time $O(\sqrt{n}m\log n)$, improving two previous $O(nm)$-time algorithms by Abraham [MSc thesis, University of Glasgow 2003] and Harvey, Ladner, Lovasz and Tamir [WADS 2003 and Journal of Algorithms 2006]. We also extend this algorithm to solve the Balance Edge Cover problem in time $O(\sqrt{n}m\log n)$, improving the previous $O(nm)$-time algorithm by Harada, Ono, Sadakane and Yamashita [ISAAC 2008].

## A deterministic near-linear time algorithm for ﬁnding minimum cuts in planar graphs (SODA’04)

We present a simple deterministic O(n log2
n)-time divide-
and-conquer algorithm for ﬁnding minimum cuts in planar
graphs. This can be compared to a randomized algorithm
for general graphs by Karger that runs in time O(mlog3
n)
and also a deterministic algorithm for general graphs by
Nagamochi and Ibaraki that runs in time O(mn+n2
log n).
We use shortest paths in the dual graphs to partition the
problem, and use the relationship between minimum cuts
in primal graphs and shortest paths in dual graphs to ﬁnd

minimum cuts that cross the partitions eﬃciently.Au

We present a simple deterministic $O(n(\log n)^2)$-time divide-and-conquer algorithm for ﬁnding minimum cuts in planar graphs. This can be compared to a randomized algorithm for general graphs by Karger that runs in time $O(m(\log n)^3)$ and also a deterministic algorithm for general graphs by Nagamochi and Ibaraki that runs in time $O(mn+n^2 \log n)$. We use shortest paths in the dual graphs to partition the problem, and use the relationship between minimum cuts in primal graphs and shortest paths in dual graphs to ﬁnd minimum cuts that cross the partitions eﬃciently.