#### SODA'18 Editorial

Yin Tat Lee; Marcin Pilipczuk; David WoodrufGiven a directed n-node graph G with integer edge weights in [-M,M], a source node s, a target node t, and an edge e, a replacement path for the triple (s,t,e) is a shortest s-t path in G avoiding e. In this paper we achieve the following main results: 1) We describe an algorithm with runtime $\tilde{O}(Mn^{\omega})$ that computes the lengths of all the replacement paths for a given source-target pair (s,t). Here $\omega<2.373$ is fast matrix multiplication exponent. For a comparison, the previous fastest algorithms have runtime $\tilde{O}(Mn^{1+2\omega/3})$ [Weimann,Yuster-FOCS'10] and $\tilde{O}(n^{2.5})$ in the unweighted case [Roditty,Zwick-ICALP'05]. 2) We describe an algorithm with runtime $\tilde{O}(M^{\frac{1}{4-\omega}}n^{2+\frac{1}{4-\omega}})$ that computes the lengths of all the replacement paths for a given source s. Our runtime reduces to $\tilde{O}(Mn^\omega)$ for positive weights, hence matching our mentioned result for the simpler case where also the target t is fixed. 3) We present a data structure (a.k.a. distance sensitivity oracle) that answers to queries of the form (s,t,e) with the length of the associated replacement path. For a given parameter $\alpha\in [0,1]$, our oracle has preprocessing time $\tilde{O}(Mn^{\omega+\frac{1}{2}}+Mn^{\omega+\alpha(4-\omega)})$ and query time $\tilde{O}(n^{1-\alpha})$. In particular, we achieve for the first time simultaneously subcubic preprocessing time and sublinear query time. For a comparison, the previous best oracle has $\tilde{O}(Mn^{\omega+1-\alpha})$ preprocessing time and (superlinear) $\tilde{O}(n^{1+\alpha})$ query time [Weimann,Yuster-FOCS'10]. All the mentioned results are randomized: a wrong distance is output with polynomially small probability in n.

The weighted $k$-server problem is a generalization of the $k$-server problem, wherein the cost of moving a server of weight $\beta_i$ through a distance $d$ is $\beta_i\cdot d$. On uniform metric spaces, this models caching with caches having different page replacement costs. A memoryless algorithm is an online algorithm whose behavior is independent of the history given the positions of its $k$ servers. In this paper, we develop a framework to analyze the competitiveness of randomized memoryless algorithms. The key technical contribution is a method for working with potential functions defined implicitly as the solution of a linear system. Using this, we establish tight bounds on the competitive ratio achievable by randomized memoryless algorithms for the weighted $k$-server problem on uniform metrics. We first prove that there is an $\alpha_k$-competitive memoryless algorithm for this problem, where $\alpha_k=\alpha_{k-1}^2+3\alpha_{k-1}+1$; $\alpha_1=1$. We complement this result by proving that no randomized memoryless algorithm can have a competitive ratio less than $\alpha_k$. Finally, we prove that the above bounds also hold for the generalized $k$-server problem on weighted uniform metrics.

The Planar Steiner Tree problem is one of the most fundamental NP-complete problems as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights, and a subset of vertices (often called terminals); the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987] considers instances where the underlying graph is planar and all terminals can be covered by the boundary of k faces. Erickson et al. show that the problem can be solved by an algorithm using n^O(k) time and n^O(k) space, where n denotes the number of vertices of the input graph. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts. In this work, we give an algorithm for Planar Steiner Tree with running time 2^O(k) n^O(\sqrt{k}) using only polynomial space. Furthermore, we show that the running time of our algorithm is almost tight: we prove that there is no f(k) n^o(\sqrt{k}) algorithm for Planar Steiner Tree for any computable function f, unless the Exponential Time Hypothesis fails.

The \emph{metric Ramsey problem} asks for the largest subset $S$ of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor \cite{MN07} devised the so called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems. In this paper we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of \emph{Ramsey Spanning Trees}. We ask for the largest subset $S\subseteq V$ of a given graph $G=(V,E)$, such that there exists a spanning tree of $G$ that has small stretch for $S$. Applied iteratively, this provides a small collection of spanning trees, such that each vertex has a tree providing low stretch paths to {\em all other vertices}. The union of these trees serves as a special type of spanner, a {\em tree-padding spanner}. We use this spanner to devise the first compact stateless routing scheme with $O(1)$ routing decision time, and labels which are much shorter than in all currently existing schemes. We first revisit the metric Ramsey problem, and provide a new deterministic construction. We prove that for every $k$, any $n$-point metric space has a subset $S$ of size at least $n^{1-1/k}$ which embeds into an ultrametric with distortion $8k$. We use this result to obtain the state-of-the-art deterministic construction of a distance oracle. ....