text:
\section{Introduction}

We begin by recalling the famous Shortest Path Tree Lemma:
\begin{lemma*} [Shortest Path Trees]
Given a node $u$ in an $n$-node graph $G = (V, E)$, there is a subgraph $H \subseteq G$ on $O(n)$ edges such that the distances of $G$ and $H$ agree on all node pairs in $\{u\} \times V$.
\end{lemma*}

Needless to say, this lemma holds a central place in theoretical computer science; it is an indispensable structural result in graph theory, and the computation of shortest path trees is one of our most basic algorithmic problems (e.g. Dijkstra's Algorithm).
This has led researchers to consider the following natural generalization: how many edges are needed in $H$ if we want the distances of $G$ and $H$ to agree on a set of node pairs $P$, which does not necessarily have the structure $P = \{u\} \times V$?

These subgraphs, which generalize shortest path trees, are called \emph{pairwise distance preservers}:
\begin{definition*} [Pairwise Distance Preservers -- \cite{CE06}, following \cite{BCE03}]
Given a graph $G = (V, E)$ and a set of node pairs $P \subseteq V \times V$, a subgraph $H \subseteq G$ is a {\em pairwise distance preserver} of $G, P$ if the distances of $G$ and $H$ agree on all node pairs in $P$.
\end{definition*}

The goal of research on distance preservers is simply to understand what the worst-case density of $H$ must be, given the number of nodes in $G$ and pairs in $P$.
A preliminary trivial lower bound is that $\Omega(n)$ edges are needed to preserve just a single pairwise distance when the underlying graph is a path, and that $\Omega(p)$ edges are needed to preserve any $p$ pairwise distances when the underlying graph is a clique.
Thus, the best upper bound we can hope for in this problem is $O(n + p)$ edges in a preserver.
Note that this bound is upper bound is realized in the case of shortest path trees; that is, $O(n + p)$ edges always suffice when $P = \{s\} \times V$.
A very fundamental question, which is an even more direct generalization of shortest path trees, is then to simply categorize when \textit{else}, if ever, we are guaranteed the existence of ``linear size distance preservers'' on $O(n + p)$ edges.
This question is the main focus of this paper.

\subsection{History}

Pairwise distance preservers were first studied by Coppersmith and Elkin \cite{CE06}, following a closely related notion of ``$D$-Preservers'' by Bollob{\' a}s, Coppersmith, and Elkin \cite{BCE03}.
Perhaps surprisingly, Coppersmith and Elkin showed that nontrivial linear size distance preservers do indeed exist: in any undirected graph, one can preserve any $p = O(n^{1/2})$ pairwise distances using a subgraph on just $O(n)$ edges.
This unexpected fact has found several interesting applications: for example, Elkin and Pettie \cite{EP15} used it to build the first linear-size $\log n$ stretch path reporting distance oracle, Bodwin and Vassilevska W. \cite{BV16} have used it to build the current most accurate additive spanner of linear size, Pettie \cite{Pettie09} used them as an ingredient in state-of-the-art constructions for mixed spanners, and they were employed by Elkin, Filtser, and Neiman \cite{EFN15} to build terminal subgraph spanners.

Coppersmith and Elkin \cite{CE06} also showed some lower bounds on the existence of linear size preservers.
They showed that $\omega(n + p)$ edges are needed to preserve $\omega(n^{1/2}) = p = \frac{n^2}{2^{\Omega(\sqrt{\log n \cdot \log \log n})}}$ pairwise distances in undirected unweighted graphs; when the underlying graph can be weighted, the range of this lower bound improves to $\omega(n^{1/2}) = p = o(n^2)$ (i.e. no further linear size preservers are possible).
These lower bounds were recently used in constructions by Abboud and Bodwin \cite{AB16so, AB16st} for spanner lower bounds; in particular, these distance preserver lower bounds were shown to imply the surprising fact that graphs cannot be compressed into $n^{4/3 - \varepsilon}$ bits while preserving distance information up to any constant additive error, thus resolving a long-standing open question about the quality of additive distance compression.

\begin{figure}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\cline{3-4}
\multicolumn{1}{l}{} && \textbf{Upper Bound} & \textbf{Lower Bound} \\
\hline
\multirow{2}{*}{\textbf{Unwtd.}} & \textbf{Undir.} & \specialcell{$O(np^{1/3} + n^{2/3}p^{2/3})$ \\and $O(n + n^{1/2}p)$\\$\mathbf{O(n)}$ \textbf{when} $\mathbf{p = O(n^{1/2})}$} & \multirow{2}{*}{\specialcell{$\Omega(n^{2d / (d^2 + 1)} p^{d(d-1)/(d^2 + 1)})$, $d \in \mathbb{N}$\\$\mathbf{\omega(n+p)}$ \textbf{when} $\mathbf{\omega(n^{1/2}) = p = o(n^{2 - o(1)})}$}} \\
\cline{2-3}
& \textbf{Dir.}  & $O(np^{1/2})$ &  \\
\hline

\multirow{2}{*}{\textbf{Wtd.}} & \textbf{Undir.} & \specialcell{$O(n + n^{1/2}p)$ and $O(np^{1/2})$\\$\mathbf{O(n)}$ \textbf{when} $\mathbf{p = O(n^{1/2})}$} & \multirow{2}{*}{\specialcell{$\Omega(n^{2/3} p^{2/3})$\\$\mathbf{\omega(n+p)}$ \textbf{when} $\mathbf{\omega(n^{1/2}) = p = o(n^2)}$}} \\
\cline{2-3}
& \textbf{Dir.}  & $O(np^{1/2})$ & \\
\hline
\end{tabular}
\end{center}
\caption{State of the art upper and lower bounds for pairwise distance preservers, for directed/undirected and weighted/unweighted graphs.  The first upper bound for undirected unweighted graphs is due to \cite{BV16}, and the remaining bounds in this chart are all due to \cite{CE06}.  The hidden $n^{o(1)}$ factor in the unweighted lower bound has the form $2^{O(\sqrt{\log n \cdot \log \log n})}$.}
\end{figure}

While applications of distance preserver bounds continue to mount (see also e.g. \cite{BCE03, BV15, ADKP15}), no further progress has been made on the existence/nonexistence of linear size distance preservers since the original paper by Coppersmith and Elkin in 2005.
Several major gaps in our knowledge of distance preservers remain.
For example, it is remarkable that \textbf{no} separations between the various graph settings are currently known: it is conceivable that the worst-case sparsity of distance preservers in directed weighted graphs is exactly the same as their worst-case sparsity in undirected unweighted graphs.
The difference between the directed and undirected settings is particularly striking here.
\emph{No} interesting linear size distance preservers are known for directed graphs; the only known upper bound of any sort is that $O(np^{1/2})$ edges suffice to preserve $p$ pairs \cite{CE06} (which has the form $O(n + p)$ only at the trivial point $p = \Omega(n^2)$).
However, on the negative side, it is not known how to improve \textit{any} of the (undirected) lower bound constructions when edge directions are allowed.
Thus, for example, techniques for reasoning about the directed setting are badly needed.

Another important setting studied by Coppersmith and Elkin is \emph{subset distance preservers}:

\begin{definition*} [Subset Distance Preservers -- \cite{CE06}]
When $P = S \times S$ for some node subset $S$ in a graph $G$, a pairwise distance preserver of $G, P$ is also called a \emph{subset distance preserver} of $G, S$.
\end{definition*}

Our picture of subset distance preservers is even fuzzier than our picture of pairwise distance preservers, in that our upper bounds do not benefit from the structure $P = S \times S$, but our lower bounds become much worse when this structure is required.
Coppersmith and Elkin proved a host of lower bounds for subset preservers, which are summarized in Figure \ref{fig:subsettable}.
Notably, our lower bounds on linear size subset preservers are \emph{polynomially} far from $s = n$; that is, it is open whether or not we can always have $O(s^2)$ sized preservers when $s = \Omega(n^{9/16})$ (unweighted graphs) or $s = \Omega(n^{3/5})$ (weighted graphs).
Confirming or refuting the existence of $O(s^2)$ size subset distance preservers when $s = n^{1 - \varepsilon}$ for any absolute $\varepsilon > 0$ is perhaps the main open question in the field of distance preservers \cite{CE06}.

\begin{figure}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\cline{3-4}
\multicolumn{1}{l}{} && \textbf{Upper Bound} & \textbf{Lower Bound}\\
\hline
\multirow{2}{*}{\textbf{Unwtd.}} & \textbf{Undir.} & \multirow{4}{*}{\specialcell{Same as pairwise preservers\\(with $s^2$ substituted for $p$)}} & \multirow{2}{*}{\specialcell{$\Omega(n^{10/11}s^{4/11} + n^{9/11}s^{6/11})$\\$\mathbf{\omega(n+s^2)}$ \textbf{when} $\mathbf{\omega(n^{1/4}) = s = o(n^{9/16})}$}} \\
\cline{2-2}
& \textbf{Dir.}  &  &  \\
\cline{1-2}\cline{4-4}

\multirow{2}{*}{\textbf{Wtd.}} & \textbf{Undir.} &  & \multirow{2}{*}{\specialcell{$\Omega(n^{6/7}s^{4/7})$\\$\mathbf{\omega(n+s^2)}$ \textbf{when} $\mathbf{\omega(n^{1/4}) = s = o(n^{3/5})}$}} \\
\cline{2-2}
& \textbf{Dir.}  & & \\
\hline
\end{tabular}
\end{center}
\caption{\label{fig:subsettable} State of the art upper and lower bounds for subset distance preservers (of $s$ nodes).  All lower bounds are due to \cite{CE06}.}
\end{figure}

\subsection{Our Results}

We show three new existence/nonexistence results for linear size distance preservers, filling in several of the gaps mentioned above.

\paragraph{$O(n)$-Sized Preservers for Directed Weighted Graphs.}

Our first result demonstrates the existence of nontrivial linear-sized preservers even in the most general setting of directed and weighted graphs.  We show:
\begin{theorem}
For any (possibly weighted and/or directed) graph $G$ on $n$ nodes, for any set $P$ of $p$ node pairs, there exists a distance preserver of $G, P$ on $O(n + n^{2/3}p)$ edges.
\end{theorem}
Thus, if $p = O(n^{1/3})$, then we have preservers of size $O(n)$.
Previously, no nontrivial upper bounds were known even for directed {\em unweighted} graphs; i.e. it was conceivable that even any $\omega(1)$ pairs would require $\omega(n)$ edges for a distance preserver in the worst case.
Our new upper bound improves on the previous upper bound of $O(np^{1/2})$ for directed weighted graphs whenever $p = o(n^{2/3})$.

This theorem is technically interesting due to its extremely short and simple proof.
Our main new idea is a simple observation that extends a certain trick, based on counting ``branchings'' between paths, into the directed setting for the first time.
Using this extension, we are able to re-apply a simple and elegant argument of \cite{CE06}, which was used to give upper bounds for distance preservers in undirected graphs, to obtain analogous bounds in the directed setting.

\paragraph{$O(p)$-Sized Preservers for Undirected Unweighted Graphs.}

Our second result establishes the existence of preservers of size $O(p)$ when $p$ is sufficiently large:

\begin{theorem} \label{thm:introuu}
For any unweighted undirected graph $G$ on $n$ nodes, for any set $P$ of $p$ node pairs in $G$, if $p = \Omega\left(\frac{n^2}{\rs(n)}\right)$ then there exists a preserver of $G, P$ on $O(p)$ edges.
\end{theorem}

Here, $\rs(n)$ is the Ruzsa-Szemer{\' e}di\ function, which is defined such that any graph whose edges can be partitioned into $n$ induced matchings has at most $\frac{n^2}{\rs(n)}$ edges.
The exact asymptotic value of $\rs(n)$ is open, but it is known that
$$2^{\Omega(\log^* n)} = \rs(n) = 2^{O(\sqrt{\log n \cdot \log \log n})}.$$
The lower bound is due to Fox \cite{Fox11} (improving on the original classic result by Ruzsa and Szemer{\' e}di \cite{RS76}).
The upper bound is implied via graphs built from dense sets that contain no arithmetic progressions.
The best such construction is due to Elkin \cite{Elk11} (improving on a classic construction of Behrend \cite{Beh46}).
It would be a major breakthrough to substantially improve either of these bounds on $\rs(n)$.
Some of the notable constructions of Ruzsa-Szemer{\' e}di\ -like graphs include \cite{AMS12, RS76, FNRRS02, BLM93}.
As this is an old problem with a very rich history, it would be impractical to fully survey its importance in mathematics here; instead, we refer the reader to the survey by Conlon and Fox \cite{CF13}.

Theorem \ref{thm:introuu} gives the first nontrivial preservers on $O(p)$ edges known in any setting.
Although our new preservers exist in a sub-polynomial range (no such theorem can hold in any polynomial range \cite{CE06}), they immediately have a number of interesting consequences:

\begin{enumerate}
\item This theorem provides the first separation between any two settings for distance preservers, in particular between the weighted and unweighted settings.
Recall that $\omega(p)$ edges are needed for undirected weighted graphs when $p = o(n^2)$.
Here, we show that $O(p)$ edges suffice in some range with $p = o(n^2)$ for undirected \emph{unweighted} graphs.

\item Recall that $\omega(n + p)$ edges are needed for preservers in undirected unweighted graphs, when $p = o\left(\frac{n^2}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right)$.
Our new theorem implies that the range of this lower bound cannot be improved at all without also implying new upper bounds for the Ruzsa-Szemer{\' e}di\ function, which will likely be very difficult.
This suggests that it may be beyond the scope of current mathematical techniques to improve the Coppersmith and Elkin distance preserver lower bounds in too serious a manner (if they are indeed improvable), since this may imply new upper bounds on $\rs(n)$.

\item This theorem provides a new technical barrier for graph compression lower bounds.
Recently, Abboud and Bodwin \cite{AB16st} showed that one cannot compress a graph into $o\left(\frac{n^{4/3}}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right)$ bits while preserving distance information up to any additive constant $+c$.
The $n^{o(1)}$ factor in the denominator here is inherited from the fact that the construction uses the Coppersmith-Elkin lower bounds on $\omega(p)$-size distance preservers as a central ingredient.
In particular, recall that the Coppersmith-Elkin lower bounds on $\omega(p)$-size preservers don't quite reach $n^2$; instead, they only go up to $n^{2 - o(1)}$, missing by precisely the same $n^{o(1)}$ factor that appears in the Abboud-Bodwin compression lower bounds.
It is tempting to try to improve the compression lower bound to $o(n^{4/3})$ by improving the $\omega(p)$ distance preserver lower bound up to $o(n^2)$.
However, our new Theorem \ref{thm:uupairwiseub} shows that this is impossible; the $n^{o(1)}$ factor is inherent in distance preserver lower bounds and cannot be entirely removed.
Thus, significant new ideas will be needed to improve the compression lower bound all the way to $o(n^{4/3})$, if true.

\item The proof of Theorem \ref{thm:uupairwiseub} overcomes a somewhat surprising technical hurdle.
It was shown in \cite{BV16} that, if one uses standard ``consistent'' methods for breaking ties between equally short paths, then no theorem of this sort will be possible; instead, the lower bound on $\omega(p)$-size distance preservers goes all the way up to $o(n^2)$.
In other words, any general construction of $O(p)$ size preservers when $p = o(n^2)$ (like the one offered by Theorem \ref{thm:uupairwiseub}) must use some new unusual method of shortest path tiebreaking.
In this paper we introduce ``lazy tiebreaking,'' which is used to sidestep this technical barrier.
Lazy tiebreaking ensures that the resulting preserver will have a very particular shortest path structure that contains many induced matchings, which lets us draw our new connections between distance preservers and the Ruzsa-Szemer{\' e}di\ function.

\end{enumerate}

\paragraph{Lower Bounds for Subset Distance Preservers}

Finally, we give new lower bounds for subset distance preservers:

\begin{theorem} \label{thm:iswlb}
There is a family of undirected weighted graphs $G$ on $n$ nodes and node subsets $S$ of size $s = s(n)$ such that every subset distance preserver of $G, S$ has $\Omega(sn^{2/3})$ edges.
\end{theorem}

\begin{theorem} \label{thm:isulb}
For any (possibly non-constant) integer $d \ge 2$, there is a family of undirected unweighted graphs $G$ on $n$ nodes and node subsets $S$ of size $s = s(n)$ such that every subset distance preserver of $G, S$ has
$$\Omega\left(n^{2d/(d^2+1)} s^{(2d-1)(d-1)/(d^2+1)}\left(\frac{1}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right)\right)$$
edges.
\end{theorem}

These imply:
\begin{corollary} \label{cor:weighted}
Subset distance preservers in (directed or undirected) weighted graphs need $\omega(s^2)$ edges in the worst case when $s = o\left(n^{2/3}\right)$.
\end{corollary}

\begin{corollary} \label{cor:unweighted}
Subset distance preservers (in directed or undirected \emph{and} weighted or unweighted graphs) need $\omega(s^2)$ edges in the worst case when $s = o\left(\frac{n^{2/3}}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right)$.
\end{corollary}

Both of these corollaries reflect a polynomial improvement in the lower bounds for $s$.
In particular, the previous lower bounds (\cite{CE06}) for weighted graphs stated that $\omega(s^2)$ edges were required when $s = o(n^{3/5})$, and for unweighted graphs only the range $s = o(n^{9/16})$ was established.
More generally, Theorem \ref{thm:iswlb} improves asymptotically over the previous lower bound for weighted subset preservers when $\omega(n^{4/9}) = s = o(n^{2/3})$, and Theorem \ref{thm:isulb} improves over the previous lower bound for unweighted subset preservers when $\omega(n^{1/3 + o(1)}) = s = o(n^{2/3 - o(1)})$.

Our proof technique is not similar to the one used for previous subset preserver lower bounds.
While the bounds in \cite{CE06} were proved using new graph constructions, our bounds are better viewed as a \emph{reduction} from the subset to the pairwise setting.
We adapt particular kind of graph replacement product used in \cite{AB16st} to compose instances of the Coppersmith and Elkin \emph{pairwise} distance preserver lower bound graphs with themselves in a careful way.
The resulting graph is a bit sparser than the original lower bound graphs, but its pair set $P$ \emph{nearly} has the structure $P = S \times S$.
We can then take $S$ to be the smallest node set that encloses $P$, and this only negligibly harms the quality of the final lower bound.
Since the Coppersmith and Elkin pairwise preserver lower bound graphs are used as a direct ingredient in our proofs, in some sense, Corollaries \ref{cor:weighted} and \ref{cor:unweighted} flow directly from the pairwise lower bounds discussed earlier, stating that $\omega(p)$ edges are needed in a pairwise preserver when $p = o\left(n^2\right)$ (weighted setting) or $p = o\left(n^2 / 2^{\Theta(\sqrt{\log n \cdot \log \log n})}\right)$ (unweighted setting).

\subsection{Other Related Work}

There has been lots of work on the relaxation of distance preservers in which distances must be preserved {\em up to an additive error term}.
These subgraphs are called {\em (additive) pairwise spanners}, or sometimes {\em $+k$ approximate distance preservers.}  This line of work was implicit in many notable papers over the last 15 years, but it was first explicitly abstracted by Cygan, Grandoni, and Kavitha \cite{CGK13}.
Later improved upper bounds came from Kavitha and Varma \cite{KV13}, Kavitha \cite{Kavitha15}, and Bodwin and Williams \cite{BV16}, and new lower bounds came from Woodruff \cite{Woo06}, Parter \cite{Parter14}, and Abboud and Bodwin \cite{AB16so, AB16st}.

More generally, the field of {\em (all pairs) spanners}, in which \emph{all} pairwise distances must be approximately preserved, has received quite a lot of research attention over the last few decades.
In this time, researchers have essentially fully understood what is possible in the regime of multiplicative error \cite{ADD+93, Awe85, PS89, girth}, nearly understood what is possible in the regime of additive error \cite{ACM96, Chechik13, BKMP10, AB16st}, and provided some surprisingly strong upper bounds in the regime of mixed (i.e. both additive and multiplicative) error \cite{Elkin05, TZ06, Pettie07, EP04, BKMP10}.
Another common variant is {\em fault-tolerant} spanners or distance preservers, which must (approximately) preserve distances even after some edges ``fail.''
Parter and Peleg \cite{PP13} obtained matching upper and lower bounds for BFS structures in the presence of one fault, and Parter \cite{Parter15} obtained upper and lower bounds for the two fault case.
Interesting fault-tolerant spanners were constructed in \cite{CLPR10, Parter14dc, DK11, BGGLP15, BCDS15}.

\setcounter{theorem}{0}
\setcounter{corollary}{0}
\section{O(n)-Sized Preservers for Directed Weighted Graphs}

In this section, we show:

\begin{theorem} \label{dwub}
Any (possibly directed and/or weighted) graph $G = (V, E)$ and set $P$ of $p$ node pairs has a distance preserver on $O(n + n^{2/3}p)$ edges.
\end{theorem}

Our first observation is that it suffices to show that any set of $p = O(n^{1/3})$ node pairs has a linear size distance preserver on $O(n)$ edges.
Given an arbitrary set of node pairs, we may then divide the pair set into groups of size $O(n^{1/3})$, build a preserver of each group individually, and then take a union bound over the (linear) sizes of each individual preserver to obtain the claimed upper bound.
We will thus focus here on this simpler problem.
Our proof is morally similar to the proof in \cite{CE06} that all undirected graphs have distance preservers on $O(n + n^{1/2}p)$ edges.

We begin with some useful background on {\em tiebreaking schemes} for shortest paths.
When the pairs in $P$ do not have unique shortest paths between them, it is necessary to break ties (i.e. choose one of the many shortest paths to include in the preserver) in some predefined way.
This notion is formalized as:
\begin{definition} [Shortest Path Tiebreaking Scheme -- \cite{BV16}]
Given a graph $G$, a {\em shortest path tiebreaking scheme} (or {\em tiebreaking scheme} for short) is a function $\pi$ that maps ordered pairs of nodes $(s, t)$ to a shortest path in $G$ from $s$ to $t$.
When the underlying graph is clear from context, we will suppress the subscript $G$.
For a set of node pairs $P$, we will commonly use $\pi(P)$ as a shorthand for $\bigcup \limits_{p \in P} \pi(p)$.
\end{definition}

The following is a useful property of tiebreaking schemes:
\begin{definition} [Consistency -- \cite{BV16}]
A tiebreaking scheme $\pi$ is {\em consistent} if, for all nodes $w, x, y, z \in V$, if $x, y \in \pi(w, z)$ with $\dist(w, x) < \dist(w, y)$, then $\pi(x, y)$ is a subpath of $\pi(w, z)$.
\end{definition}

Note that all graphs admit a consistent tiebreaking scheme:
\begin{claim}
For any graph $G$, there is a tiebreaking scheme $\pi$ that is consistent in $G$.
\end{claim}
\begin{proof}
One such tiebreaking scheme can be obtained as follows: let $\Delta$ be the minimum positive difference between any two shortest path lengths, and then randomly perturb each edge weight in $G$ by a number drawn uniformly at random from the interval $\left[0, \frac{\Delta}{3n}\right]$.
Since each shortest path uses at most $n$ edges, this process changes the length of any path by at most $\frac{\Delta}{3}$, and thus it cannot cause a previously non-shortest path between two nodes to become shortest.
Additionally, with probability 1, no two sets of edges will have equal total weight; thus, shortest paths in the new graph $G'$ with perturbed edge weights are unique.
We now define $\pi$ to be the tiebreaking scheme in $G$ that chooses the (unique) shortest path between two nodes in the perturbed graph $G'$.
\end{proof}

To construct distance preservers implementing Theorem \ref{dwub}, simply choose shortest paths between the pairs in $P$ according to any consistent tiebreaking scheme.
That is, our preserver is the graph $H = (V, E_H := \pi(P))$ for some consistent tiebreaking scheme $\pi$.
We will now begin to prove upper bounds on the size of this edge set $E_H$.
The proof is a counting argument, based on the following definition:
\begin{definition} [Branching Triple]
A {\em branching triple} is a set of three distinct (directed) edges $\{e_1 = (u_1, v), e_2 = (u_2, v), e_3 = (u_3, v)\}$ that all enter the same node.
\end{definition}

\begin{lemma} \label{lem:brtrip} $H$ has at most $\binom{p}{3}$ branching triples.
\end{lemma}
\begin{proof}
For each edge $e$ in $H$, assign ownership of $e$ to some pair $p \in P$ such that $e \in \pi(p)$.  We will prove the claim by arguing that there do not exist any two branching triples
$$t = \{e_1 = (u_1, v), e_2 = (u_2, v), e_3 = (u_3, v)\} \text{  and  } t' = \{e'_1 = (u'_1, v'), e'_2 = (u'_2, v'), e'_3 = (u'_3, v')\}$$
with their edges owned by the same set of three pairs $p_1, p_2, p_3$ (with $e_i$ and $e'_i$ owned by $p_i$ for each $i \in \{1, 2, 3\}$).  Suppose towards a contradiction that $t, t'$ exist as described.

Assume without loss of generality that at least two of the three edges $e_i \in t$ precede the corresponding edge $e'_i \in t'$ in their respective paths $p_i$.
More specifically, we assume that $e_1$ precedes $e'_1$ in $p_1$ and $e_2$ precedes $e'_2$ in $p_2$.
It follows that $v, v' \in \pi(p_1)$ (with $v$ preceding $v'$), and also $v, v' \in \pi(p_2)$ (again with $v$ preceding $v'$).
Since $\pi$ is consistent, this means that $\pi(v, v')$ is a subpath of both $p_1$ and $p_2$.
Therefore, $p_1$ and $p_2$ both contain the same edge entering $v'$, and so $e'_1 = e'_2$.
However, by definition, all edges must be unique within any branching triple.
By contradiction, then, $t$ and $t'$ cannot be owned by the exact same set of three pairs, and the lemma follows.
\end{proof}

\begin{claim}
A graph with $O(n)$ branching triples has $O(n)$ edges.
\end{claim}
\begin{proof}
Consider adding $O(n)$ edges one by one to an initially empty graph.
The first and second edge entering a node do not create any new branching triples.
Each subsequent edge creates (at least) one new branching triple.
Therefore, the number of edges in the graph is at most $2n$ more than the number of branching triples in the graph.
\end{proof}
It now follows straightforwardly that all $G, P$ has a preserver on $O(n)$ edges whenever $|P| = O(n^{1/3})$, which implies Theorem \ref{dwub}.

\section{O(p)-Sized Preservers for Undirected Unweighted Graphs}

The following definitions will be useful in this section:

\begin{definition} [Induced Matching]
Given an undirected unweighted graph $G = (V, E)$, a set of edges $E' \subseteq E$ is an {\em induced matching} if $E'$ is a matching, and there exists a set of nodes $S \subseteq V$ such that edges in the subgraph $G[S]$ of $G$ induced on $S$ are exactly $E'$.
\end{definition}

\begin{definition} [Ruzsa-Szemer{\' e}di\ Graph]
A (undirected unweighted) graph $G = (V, E)$ is a {\em Ruzsa-Szemer{\' e}di\ graph} if its edge set can be partitioned into at most $n$ induced matchings.
\footnote{Standard terminology is that a graph is an $(r, t)$-Ruzsa-Szemer{\' e}di\ graph if its edges can be partitioned into $t$ induced matchings, each of size exactly $r$.  In this paper we suppress the leading $(r, t)$ because we exclusively consider $t = n$, and we omit the detail that the matchings must have the same size (which affects all relevant functions only by a constant factor).}
\end{definition}

\begin{definition} [$\rs(n)$]
The function $\rs(n)$ is defined to be the largest value such that every Ruzsa-Szemer{\' e}di\ graph on $n$ nodes has at most $\frac{n^2}{\rs(n)}$ edges.
\end{definition}

See the introduction for more details on the function $\rs(n)$.  We will show:
\begin{theorem} \label{thm:uupairwiseub} Any undirected unweighted graph $G = (V, E)$ and set $P$ of $p = \Omega\left(\frac{n^2}{\rs(n)}\right)$ node pairs has a distance preserver on $O(p)$ edges.
\end{theorem}

\subsection{Reduction to the Bipartite Setting}

For technical reasons, our main proof of the sparsity of $H$ will require an assumption that the underlying graph is bipartite.
Here, we show that this assumption can be made while essentially only paying negligible cost in the preserver density.
A similar reduction, which contains different terminology and is not strong enough for our purposes here, appeared in \cite{AB16so} (although this reduction was used for a very different reason).

We remark that it is not strictly necessary to include this graph transformation as part of the preserver \emph{construction}; that is, Theorem \ref{thm:uupairwiseub} applies even if we perform the construction in Section \ref{sec:lazy} to the original non-bipartite graph.
We would then imagine performing the reduction in this section to the preserver solely for the sake of the analysis.
However, it simplifies the proofs a bit (if not the construction) to preprocess the graph to be bipartite, so we present our construction in this order.\footnote{This observation was suggested by an anonymous reviewer.}

\begin{lemma} \label{lem:bptred}
Suppose that every distance preserver of a bipartite graph $G$ and set $P$ of $p$ node pairs has at most $f(n, p)$ edges.
Then every distance preserver of an arbitrary graph $G$ and a set $P$ of $p$ node pairs has at most $f(2n, 2p)$ edges.
\end{lemma}
This lemma holds in any setting; e.g. it is true both for directed weighted graphs and undirected unweighted graphs.
In this paper, however, we will only apply it in the undirected unweighted setting.

Our main transformation is the \emph{bipartite preserver lift}:
\begin{definition} [Bipartite Preserver Lift]
Given a graph $G = (V, E)$ and a set of node pairs $P$, the \emph{bipartite preserver lift} of $G, P$ is a bipartite graph $G' = ((V_1, V_2), E')$ and a set of node pairs $P'$ in $G'$ defined as follows:
\begin{itemize}
\item $V_1$ and $V_2$ are both identical copies of $V$.  For any node $x \in V$, we will use the subscript $x_1$ ($x_2$) to denote the corresponding node in $V_1$ ($V_2$).
\item For each edge $(u, v) \in E$, we include edges $(u_1, v_2)$ and $(u_2, v_1)$ in $E'$ .
\item For each pair $(s, t) \in P$, if $\dist_G(s, t)$ is even, then we include pairs $(s_1, t_1), (s_2, t_2) $ in $P'$.  If $\dist_G(s, t)$ is odd, then instead we include pairs $(s_1, t_2), (s_2, t_1)$ in $P'$.
\end{itemize}
\end{definition}

We call the (nearly) inverse operation to the bipartite lift a \emph{contraction}:
\begin{definition} [Contraction]
Let $G' = (V_1 \cup V_2, E'), P'$ be the bipartite preserver lift of some $G = (V, E), P$, and let $H' = (V_1 \cup V_2, E'_H) \subseteq G'$.  The \emph{contraction} of $H'$ is a graph $H = (V, E_H) \subseteq G$, where
$$E_H := \{(u, v) \in V \times V \ \mid \ (u_1, v_2) \in E'_H \text{ or } (u_2, v_1) \in E'_H\}.$$
\end{definition}

\begin{claim} \label{clm:pathlen}
Let $G', P'$ be the bipartite lift of some $G, P$.  Then for any pair $(s_i, t_j) \in P'$ (where $i, j \in \{1, 2\}$), we have $\dist_{G'}(s_i, t_j) \le \dist_{G}(s, t)$.\footnote{In fact $\dist_{G'}(s_i, t_j) = \dist_G(s, t)$, but we will only need to show this weaker fact.}
\end{claim}
\begin{proof}
We will prove the claim for the case $i = j = 1$; the other settings of $i, j$ follow from a symmetric argument.

Let $q = (s, x^1, \dots, x^{k-1}, t)$ be a shortest path from $s$ to $t$ in $G$.  Note that by construction, the existence of $(s_1, t_1) \in P'$ implies that $\dist_G(s, t)$ is even, and so $k-1$ is odd.  Therefore, we have a path mirroring $q$ of the form $(s_1, x^1_2, \dots, x^{k-1}_2, t_1)$ in $G'$, and so there exists a path in $G'$ of length $k$ from $s_1$ to $t_1$.  Thus, $\dist_{G}(s, t) = k \ge \dist_{G'}(s_1, t_1)$.
\end{proof}

We now have:
\begin{claim} \label{bptred}
Let $G = (V, E)$ be a graph and let $P$ be a set of node pairs in $G$.  Then if $H'$ is a preserver of the bipartite preserver lift $G', P'$ of $G, P$, then the contraction $H$ of $H'$ is a preserver of $G, P$.
\end{claim}
\begin{proof}
Consider any pair $(s, t) \in P$.  Assume that $\dist_G(s, t)$ is even; the case in which $\dist_G(s, t)$ is odd follows from a symmetric argument.  By construction we have $(s_1, t_1) \in P'$, and by Claim \ref{clm:pathlen} we know that $\dist_{G'}(s_1, t_1) \le \dist_G(s, t)$.  Thus, there exists a path from $s_1$ to $t_1$ in $H'$ of length at most $\dist_G(s, t)$.  Let
$$q' := (s_1, x^1_2, \dots, x^{k-1}_2, t_1)$$
be this path.  By construction, there exists a path
$$q = (s, x^1, \dots, x^{k-1}, t)$$
in $H$.  It follows that $\dist_H(s, t) \le \dist_G(s, t)$.  To complete the proof, we will argue that $H \subseteq G$, and so $\dist_H(s, t) = \dist_G(s, t)$ and $H$ is a preserver of $G, P$.  The fact that $H \subseteq G$ follows quite simply from the definitions of preserver lifts and contractions: if there is an edge $(u, v)$ in $H$, then there is an edge $(u_1, v_2)$ or $(u_2, v_1)$ in $H'$; since $H' \subseteq G'$ this edge is also in $G'$, and thus we have that $(u, v)$ is an edge in $G$.
\end{proof}

Given our preserver $H$, we then arbitrary graph $G$, we may then prove Lemma \ref{lem:bptred} by computing a bipartite lift $G', P'$ of $G,P$, building a preserver $H'$ of $G', P'$ on $f(2n, 2p)$ edges, and then contracting $H'$ back down to a graph $H$ on at most $f(2n, 2p)$ edges which is a preserver of $G, P$.

We proceed with the assumption that the underlying graph $G$ in Theorem \ref{thm:uupairwiseub} is bipartite.

\subsection{Lazy Tiebreaking \label{sec:lazy}}

We will first describe the tiebreaking scheme used to build our preserver.  First, we need some new notation.

\begin{definition} [$P_s$]
Given a graph $G = (V, E)$ and a set of node pairs $P$, for any node $s \in V$, the set $P_s$ is defined as the subset of pairs in $P$ with source node $s$.  That is, $P_s := \{(s, t) \in P \ \mid \ t \in V\}.$
\end{definition}

\begin{definition} [Branching Edges]
In a tree $T$ rooted at a node $s$, a node $b$ is a branching node if, when the edges of $T$ are oriented away from $s$, we have $\deg_{out}(b) \ge 2$.  Any edge leaving a branching node $b$ under this orientation of $T$ is then called a {\em branching edge}.  The set of branching edges of $T$ is denoted $\mathcal{B}(T)$.
\end{definition}

\begin{definition} [Lazy Tiebreaking]
A tiebreaking scheme $\pi$ in a graph $G = (V, E)$ is called {\em lazy} for a pair set $P$ if:
\begin{enumerate}
\item For all $s \in V$, the graph $T_s := (V, \pi(P_s))$ is a tree (possibly together with some isolated nodes), and

\item For all distinct non-branching edges $(x, y), (x', y') \in T_s \setminus \mathcal{B}(T_s)$ with $\dist_G(s, y) = \dist_G(s, y') = \dist_G(s, x)+1 = \dist_G(s, x')+1$, we have $(x, y') \notin E$ (and, by symmetry, $(x', y) \notin E$)
\end{enumerate}
\end{definition}

Informally, a tiebreaking scheme is ``lazy'' if it tries to delay the branching edges of $T_s$ for as long as possible.
This follows from the definition because, if the second requirement of lazy tiebreaking is violated -- i.e. $(x', y) \in E$ -- then we can re-choose the path from $s$ to $y$ such that it passes through $x$ instead of $x'$, and this will delay its final branching edge.

All graphs and sets of node pairs admit a lazy tiebreaking scheme:
\begin{claim}
For any graph $G$ and set of node pairs $P$, there is a tiebreaking scheme $\pi$ in $G$ that is lazy for $P$.
\end{claim}
\begin{proof}
Note from the definition of lazy tiebreaking that it suffices to only consider a pair set $P = P_s$ in which all pairs have the same source node $s$.
Let $\mathcal{T}$ be the set of all preservers of $P_s$ in $G$ that are trees (possibly together with some isolated nodes).
For any $T_s \in \mathcal{T}$, sort the branching edges $\mathcal{B}(T_s)$ in descending order by distance from $s$, and let $\mathcal{D}(T_s)$ be the (descending) list of these distances.
We now define a partial ordering over the elements of $\mathcal{T}$: say that $T_s < T'_s$ if $\mathcal{D}_i(T_s) < \mathcal{D}_i(T'_s)$ for the first index $i$ on which the two lists differ (if the lists are identical, or one is a prefix of the other, then $T_s, T'_s$ are incomparable).
Now choose any maximal element $T^{\max}_s$ in this partial ordering.
We will argue that the corresponding tiebreaking scheme $\pi$ such that $\pi(P_s) = T^{\max}_s$ is lazy.

To see this, assume towards a contradiction that $\pi$ is \emph{not} lazy; that is, there are distinct non-branching edges $(x, y), (x', y') \in T^{\max}_s \setminus \mathcal{B}(T^{\max}_s)$ with $\dist_G(s, y) = \dist_G(s, y') = \dist_G(s, x) + 1 = \dist_G(s, x') + 1$ and $(x, y') \in E$.
We may then define a new tiebreaking scheme $\pi'$, which reroutes all paths containing the edge $(x', y')$ such that they now follow $T^{\max}_s$ from $s$ to $x$, then walk the edge $(x, y')$, and then continue along their old suffix to their non-$s$ endpoint (for pairs that do not use the edge $(x', y')$ under $\pi$, we define $\pi'$ to agree with $\pi$).
Note that in $\pi'(P_s)$, the edge $(x, y)$ is a branching edge, whereas it is not a branching edge in $\pi(P_s)$.
Further, $\pi(P_s)$ and $\pi'(P_s)$ have exactly the same set of edges at distance further than $(x, y)$ from $s$.
Additionally, observe that $(x', y')$ is the only edge that is equally far from $s$ as $(x, y)$ that belongs to $\pi(P_s)$ but not $\pi'(P_s)$.
Since we have assumed that $(x', y')$ is not a branching edge, these three conditions imply that $\pi'(P_s) > \pi(P_s) = T^{\max}_s$.
This contradicts the assumption that $T^{\max}_s$ is a maximal element in the partial ordering; thus, $\pi$ is lazy.
\end{proof}

A preserver implementing Theorem \ref{thm:uupairwiseub} may be built using any lazy tiebreaking scheme: that is, our preserver is $H := (V, E_H := \pi(P))$ for some $\pi$ that is lazy for $P$.

\subsection{Proof of Correctness}

\begin{lemma} \label{lem:matchpartition}
The edges of $E_H \setminus \bigcup \limits_{s \in V} \mathcal{B}(T_s)$ can be partitioned into $3n$ induced matchings.
\end{lemma}
\begin{proof}
For each edge
$$e = (u_1, v_2) \in E_H \setminus \bigcup \limits_{s \in V} \mathcal{B}(T_s)$$
assign $e$ to a node $s$ such that $e \in T_s$.
Next, for each $s \in V$, partition the edges owned by $s$ into three equivalence classes $C_s^{0}, C_s^{1}, C_s^{2}$.
Each edge $(u, v)$, with $\dist_{G}(s, u) < \dist_{G}(s, v)$, is assigned to the class $C_s^i$ where $i := \dist_{G}(s, u) \mod 3$.  There are $3n$ such classes in total.
We will now show that each class is an induced matching.

Let $(u, v), (w, x) \in C_s^{i}$ for some $s \in V, i \in \{0, 1, 2\}$.  Assume without loss of generality that $\dist_{G}(s, u) \le \dist_{G}(s, w)$.  We split into two cases:

First, suppose $\dist_{G}(s, u) + 3 \le \dist_G(s, w)$, and so we additionally have $\dist_{G}(s, u) + 4 \le \dist_{G}(s, x)$.  Then none of the edges $(u, w), (u, x), (v, w), (v, x)$ may exist in $G$, as any one of these edges would imply the existence of a path from $u$ to $x$ of length $3$ or less.

Since $(u, v), (w, x) \in C_s^{i}$ for some $i$, the only other case to consider is when $\dist_{G}(s, u) = \dist_{G}(s, w)$, and thus also $\dist_{G}(s, v) = \dist_{G}(s, x)$.  In this case, we first observe that $(u, w), (v, x) \notin E$, since this would give us an odd cycle $s \leadsto u \to w \leadsto s$ or $s \leadsto v \to x \leadsto s$ (which cannot exist since $G$ is bipartite).  Second, we note that $(u, x), (v, w) \notin E$ by the second property of lazy tiebreaking.

We now have that $(u, w), (u, x), (v, w), (v, x) \notin E$.  Consider the graph induced on the endpoints of all edges in some particular $C_s^i$.  It follows that the edge set of this graph is \emph{precisely} the set of edges in $C_s^i$, and so each $C_s^i$ is an induced matching.
\end{proof}

\begin{claim} \label{clm:bredges}
$\left|\bigcup \limits_{s \in V} \mathcal{B}(T_s)\right| = O(p)$
\end{claim}
\begin{proof}
For any fixed $s$, the tree $T_s$ has at most $|P_s|$ leaves; thus, by standard structure of trees, it has $O(|P_s|)$ branching edges.  We then have
$$
\left|\bigcup \limits_{s \in V} \mathcal{B}(T_s) \right| = \sum \limits_{s \in V} O(|P_s|) = O(p)
$$
where the second equality follows from the fact that the collection $\{P_s\}$ over all $s \in V$ is a partition of $P$.\footnote{It is convenient here to interpret the pairs in $P$ as ordered, so that a single pair $(s, t) \in P$ is not considered in both $P_s$ and $P_t$.}
\end{proof}

\begin{lemma} \label{lem:presexist}
$$|E_H| = O(p) +  O\left(\frac{n^2}{\rs(n)} \right)$$
\end{lemma}
\begin{proof}
Define a new graph $R \subseteq H$ as follows.  First, remove all edges in $\bigcup \limits_{s \in V} \mathcal{B}(T_s)$ from $E_H$.
By Lemma \ref{lem:matchpartition}, the remaining graph can be partitioned into $3n$ induced matchings; keep all edges in the $n$ largest matchings (breaking ties arbitrarily) and discard the rest.
Clearly we discard only a constant fraction of the edges in this way.
The remaining edge set $E_R$ can be partitioned into $n$ induced matchings, so it is a Ruzsa-Szemer{\' e}di\ graph.  Thus, we have
$$|E_R| \le \frac{n^2}{\rs(n)}$$
and so
$$|E_H| = O\left( \frac{n^2}{\rs(n)} \right) + \left| \bigcup \limits_{s \in V} \mathcal{B}(T_s) \right|.$$
By Claim \ref{clm:bredges}, we then have
$$|E_H| = O\left( \frac{n^2}{\rs(n)} \right) + O(p).$$
\end{proof}

We can now show:
\begin{proof} [Proof of Theorem \ref{thm:uupairwiseub}]
Let $f(n, p)$ be the maximum number of edges needed in a preserver of an undirected unweighted bipartite graph on $n$ nodes and a set of $p$ node pairs.
By Lemma \ref{lem:presexist}, we have
$$f(n, p) = O \left( \frac{n^2}{\rs(n)} \right) + O(p)$$
By Lemma \ref{lem:bptred}, the maximum number of edges needed in a preserver of a (not necessarily bipartite) graph on $n$ nodes and a set of $p$ node pairs is
$$f(2n, 2p) = O \left( \frac{(2n)^2}{\rs(2n)}\right) + O(2p) = O \left( \frac{n^2}{\rs(2n)}\right) + O(p)$$
Clearly $\rs(2n) \ge \rs(n)$, and so we have
$$f(2n, 2p) = O \left( \frac{n^2}{\rs(n)}\right) + O(p)$$
Thus, if $p = \Omega \left( \frac{n^2}{\rs(n)} \right)$, then we have $f(2n, 2p) = O(p)$, which completes the proof.
\end{proof}

\section{Lower Bounds for Subset Preservers}

We show:
\begin{theorem} \label{thm:swlb}
For any $s = s(n)$, there is a family of undirected weighted graphs $G = (V, E)$ and sets $S$ of $s$ nodes in $G$ such that any subset distance preserver of $G, S$ has $\Omega(n^{2/3}s)$ edges.
\end{theorem}

\begin{theorem} \label{thm:sulb}
For any integer $d \ge 2$, for any $s = s(n)$, there is a family of undirected unweighted graphs $G = (V, E)$ and sets $S$ of $s$ nodes in $G$ such that any subset distance preserver of $G, S$ has
$$\Omega\left(n^{2d/(d^2+1)} s^{(2d-1)(d-1)/(d^2+1)}\left(\frac{1}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right)\right)$$
edges.
\end{theorem}

These imply:
\begin{corollary}
Subset distance preservers in (directed or undirected) weighted graphs need $\omega(s^2)$ edges in the worst case when $s = o(n^{2/3})$.
\end{corollary}
\begin{proof}
Immediate from Theorem \ref{thm:swlb}.
\end{proof}
\begin{corollary}
Subset distance preservers (in directed or undirected \emph{and} weighted or unweighted graphs) need $\omega(s^2)$ edges in the worst case when
$$s = o\left(\frac{n^{2/3}}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right).$$
\end{corollary}
\begin{proof}
By direct calculation, the lower bound in Theorem \ref{thm:sulb} is $\omega(s^2)$ when
$$s = \omega\left(n^{2d/(3d+1)} / 2^{\Theta(\sqrt{\log n \cdot \log \log n})} \right) = \omega\left(n^{2/3 - 2/(9d+3)} / 2^{\Theta(\sqrt{\log n \cdot \log \log n})} \right).$$
We now choose $d = \Theta\left(\sqrt{\log n / (\log \log n)}\right)$, and so
$$n^{2/(9d+3)} = n^{1/\Theta\left(\sqrt{\log n / (\log \log n)}\right)} = n^{\Theta\left(\sqrt{(\log \log n) / \log n}\right)} = 2^{\Theta\left(\sqrt{\log n \cdot \log \log n}\right)}$$
Thus, the lower bound is $\omega\left(s^2\right)$ when
$$s = \omega \left(n^{2/3} / 2^{\Theta(\sqrt{\log n \cdot \log \log n})} \right)$$
and the corollary follows.
\end{proof}

We now give the proofs of Theorems \ref{thm:swlb} and \ref{thm:sulb}.
We begin in the weighted setting, which is a bit simpler.

\subsection{The Weighted Construction}

We begin the discussion by recalling the weighted \emph{pairwise} lower bounds of Coppersmith and Elkin:
\begin{theorem} [\cite{CE06}] \label{thm:cewlb}
For any $n$, there is a graph $G$ on $n$ nodes and a set $P$ of $p = p(n)$ node pairs such that any distance preserver of $G, P$ has $\Omega\left(n^{2/3}p^{2/3}\right)$ edges.
\end{theorem}

Let us first give an informal overview of the proof.
Our goal is to convert the Coppersmith and Elkin pairwise lower bound graph into a lower bound for subset preservers.
It is tempting to simply define $S$ to be the set of nodes consisting of all endpoints in $P$; then clearly a subset preserver of $G, S$ will need $\Omega(n^{2/3}p^{2/3})$ edges.
Unfortunately, a closer look at the Coppersmith and Elkin construction reveals that this straightforward approach will fail:
\begin{itemize}
\item We suffer some ``cost'' for using $S \times S$ in place of $P$, since all pairs in $(S \times S) \setminus P$ are ``useless'' -- i.e. we must count them in our pair set, but they are not being used to enforce that any particular shortest path remains in the lower bound graph.
Let $L = \frac{s^2}{p}$ capture this cost.

\item The ``value'' of a useful pair in $P$ is the number of edges that it adds to the preserver lower bound.
It turns out that the value of each pair in $P$ is $L$ (up to constant factors).
In other words, the cost \emph{exactly} offsets the value in this approach; that is, the \emph{average} value of a pair in $S \times S$ is only $O(1)$, so this naive construction only yields the trivial lower bound of $\Omega(s^2)$.
\end{itemize}

\begin{figure}[t!]
\centering
\begin{subfigure}{.4\textwidth}
\begin{center}
\begin{tikzpicture}

\draw [ultra thick, red] (-0.85, 0) -- (0.85, 0);
\draw [ultra thick, blue] (-0.5, 0.7) -- (0.5, -0.7);
\draw [ultra thick, green] (0.5, 0.7) -- (-0.5, -0.7);

\draw [thick, red, dotted] plot [smooth] coordinates {(-2, 0) (-0.85, 0) (0.85, 0) (2, -0)};
\draw [thick, blue, dotted] plot [smooth] coordinates {(-1, 2) (-0.5, 0.7) (0.5, -0.7) (1, -2)};
\draw [thick, green, dotted] plot [smooth] coordinates {(-1, -2) (-0.5, -0.7) (0.5, 0.7) (1, 2)};

\draw [fill=red] (-2, 0) circle [radius=0.15cm];
\draw [fill=red] (2, 0) circle [radius=0.15cm];
\draw [fill=blue] (-1, 2) circle [radius=0.15cm];
\draw [fill=blue] (1, -2) circle [radius=0.15cm];
\draw [fill=green] (1, 2) circle [radius=0.15cm];
\draw [fill=green] (-1, -2) circle [radius=0.15cm];

\draw [fill=black] (0, 0) circle [radius=0.15cm];
\node at (0, -0.5) {$v$};

\end{tikzpicture}
\end{center}
\caption{Let $v$ be a node in a distance preserver lower bound such that three pairs in $P$ have a unique shortest path incident on $v$.}
\end{subfigure}
\hspace{.1\textwidth}
\begin{subfigure}{.4\textwidth}
\begin{center}
\begin{tikzpicture}

\draw [ultra thick, red] (-0.85, 0) -- (0.85, 0);
\draw [ultra thick, blue] (-0.5, 0.7) -- (0.5, -0.7);
\draw [ultra thick, green] (0.5, 0.7) -- (-0.5, -0.7);
\draw [fill=black] (0, 0) circle [radius=0.15cm];

\draw [thick, red, dotted] plot [smooth] coordinates {(-2, 0) (-0.85, 0) (0.85, 0) (2, -0)};
\draw [thick, blue, dotted] plot [smooth] coordinates {(-1, 2) (-0.5, 0.7) (0.5, -0.7) (1, -2)};
\draw [thick, green, dotted] plot [smooth] coordinates {(-1, -2) (-0.5, -0.7) (0.5, 0.7) (1, 2)};

\draw [fill=red] (-2, 0) circle [radius=0.15cm];
\draw [fill=red] (2, 0) circle [radius=0.15cm];
\draw [fill=blue] (-1, 2) circle [radius=0.15cm];
\draw [fill=blue] (1, -2) circle [radius=0.15cm];
\draw [fill=green] (1, 2) circle [radius=0.15cm];
\draw [fill=green] (-1, -2) circle [radius=0.15cm];

\draw [black, ultra thick, fill=white] (0, 0) circle [radius=0.5cm];
\node at (0, -0.8) {$G_v$};

\draw [fill=red] (-0.4, 0) circle [radius=0.1cm];
\draw [fill=red] (0.4, 0) circle [radius=0.1cm];
\draw [red, ultra thick, dashed] (-0.5, 0) -- (0.5, 0);
\draw [fill=blue] (-0.25, 0.33) circle [radius=0.1cm];
\draw [fill=blue] (0.25, -0.33) circle [radius=0.1cm];
\draw [blue, ultra thick, dashed] (-0.25, 0.33) -- (0.25, -0.33);
\draw [fill=green] (0.25, 0.33) circle [radius=0.1cm];
\draw [fill=green] (-0.25, -0.33) circle [radius=0.1cm];
\draw [green, ultra thick, dashed] (0.25, 0.33) -- (-0.25, -0.33);

\node [red] at (-0.7, 0.2) {$w$};
\node [red] at (0.7, 0.2) {$w$};
\node [blue] at (-0.2, 0.7) {$w$};
\node [blue] at (0.6, -0.5) {$w$};
\node [green] at (-0.6, -0.5) {$w$};
\node [green] at (0.2, 0.7) {$w$};

\end{tikzpicture}
\end{center}

\caption{We can then replace $v$ with a new distance preserver lower bound graph $G_v, P_v$ with $|P_v| = 3$, and the three paths through $v$ ``enforce'' that we preserve the three internal shortest paths for $P_v$ in $G_v$.  For technical reasons, it is also necessary to place large edge weights $w$ on edges surrounding $G_v$ (this implicitly ``penalizes'' paths that enter/leave $G_v$ not through one of the three desired internal node pairs).}
\end{subfigure}

\caption{\label{fig:op} The Obstacle Product technique lets us replace nodes in a distance preserver lower bound graph with entire new lower bound graphs.}
\end{figure}

We fix the construction by applying the \emph{obstacle product} technique of \cite{AB16st} (see Figure \ref{fig:op}).
The main idea here is that we can replace a single node $v$ in a distance preserver lower bound graph with a copy $G_v$ of a distance preserver lower bound graph, and the result is still a valid distance preserver lower bound graph.
In our construction, we use the obstacle product to replace only \emph{intermediate} nodes (i.e. nodes \emph{not} in $S$) in the Coppersmith and Elkin pairwise lower bound graph.
Thus, the ``cost'' of applying the stucture $P = S \times S$ remains unchanged, but our useful pairs must now pass through $\approx L$ \emph{copies of $G_v$} rather than $\approx L$ \emph{nodes}.
Since it takes a super-constant number of edges to cross a copy of $G_v$, our value improves enough that we obtain an interesting subset preserver lower bounds.\\

We now give the construction in more formality.
We first define an \emph{inner graph} and an \emph{outer graph}, where the outer graph is the original pairwise preserver lower bound, and the inner graph will be used to replace some of the nodes of the outer graph.
The outer graph is always the following instantiation of Theorem \ref{thm:cewlb} (regardless of the desired size of $s$):
\begin{theorem} [\cite{CE06}] \label{thm:ceouter}
There is an infinite family of $3$-layered undirected weighted graphs $G$ with $n$ nodes per layer and $\Omega(n^2)$ edges, as well as a set $P_O$ of $p_O$ node pairs with one point in the first layer and the other point in the last layer, such that:
\begin{enumerate}
\item All nodes in the middle layer have the same even degree $D = \Theta(n)$.
\item For all $(s, t) \in P_O$, there is a unique shortest path in $G$ from $s$ to $t$, and it includes exactly two edges.
\item For each edge in $G$, there is a unique pair in $P_O$ whose shortest path includes that edge.
\end{enumerate}
\end{theorem}

Our outer graph is precisely one of these three-layered graphs.
We now modify our outer graph by replacing every node in the middle layer with an \emph{inner graph} drawn from Theorem \ref{thm:cewlb}.
The specific process of replacing a node with an inner graph proceeds as follows.
Let $v$ be a node in the middle layer of the outer graph which we desire to replace.
Let the inner graph $G_I^v$ be a distance preserver lower bound graph from Theorem \ref{thm:cewlb}, instantiated with:
\begin{itemize}
\item Pair set $P_I^v$ of size $\left| P_I^v \right| = p_I = \frac{D}{2}$ node pairs and
\item $I$ nodes, for some $I \ge \Omega(D^2)$ that is a parameter of the construction.
\end{itemize}
We remove $v$ from the graph and insert a copy of $G_I$ called $G_I^v$ into the graph.
For each edge $(c, v)$ that used to be incident on $v$, we replace the edge with $(c, v')$ for some node $v' \in G_I^v$, chosen by the following process:

By Theorem \ref{thm:ceouter}, we may partition the $D$ edges incident on $v$ into $\frac{D}{2}$ pairs, where for each pair of edges $\{(c, v), (v, z)\}$ we have $(c, z) \in P_O$ and the unique shortest $c \leadsto z$ path consists of exactly these two edges.
For each such pair of edges $\{(c, v), (v, z)\}$, choose any distinct node pair $(q, r) \in P_I^v$, and replace the old edges $(c, v), (v, z)$ with new edges $(c, q), (r, z)$.
The weights of these edges remain unchanged (for now), i.e. $w_{(c, v)} = w_{(c, q)}$ and $w_{(v, z)} = w_{(r, z)}$.
We replace every node $v$ in the middle layer of the outer graph with a distinct copy $G_I^v$ in this manner.

\begin{figure}
\begin{center}
\begin{tikzpicture}
\draw (0,0) ellipse (1cm and 2cm);
\draw (5,0) ellipse (2cm and 4cm);
\draw (10,0) ellipse (1cm and 2cm);

\draw [ultra thick] (5, 0) circle [radius=1cm];
\draw [ultra thick] (5, 2.5) circle [radius=1cm];
\draw [ultra thick] (5, -2.5) circle [radius=1cm];

\draw [fill=black] (4.4, 0) circle [radius=0.1cm];
\draw [fill=black] (4.4, 0.4) circle [radius=0.1cm];
\draw [fill=black] (4.4, -0.4) circle [radius=0.1cm];

\draw [fill=black] (4.4, 2.9) circle [radius=0.1cm];
\draw [fill=black] (4.4, 2.1) circle [radius=0.1cm];
\draw [fill=black] (4.4, 2.5) circle [radius=0.1cm];

\draw [fill=black] (4.4, -2.9) circle [radius=0.1cm];
\draw [fill=black] (4.4, -2.1) circle [radius=0.1cm];
\draw [fill=black] (4.4, -2.5) circle [radius=0.1cm];

\draw [fill=black] (5.6, 0) circle [radius=0.1cm];
\draw [fill=black] (5.6, 0.4) circle [radius=0.1cm];
\draw [fill=black] (5.6, -0.4) circle [radius=0.1cm];

\draw [fill=black] (5.6, 2.9) circle [radius=0.1cm];
\draw [fill=black] (5.6, 2.1) circle [radius=0.1cm];
\draw [fill=black] (5.6, 2.5) circle [radius=0.1cm];

\draw [fill=black] (5.6, -2.9) circle [radius=0.1cm];
\draw [fill=black] (5.6, -2.1) circle [radius=0.1cm];
\draw [fill=black] (5.6, -2.5) circle [radius=0.1cm];

\draw [thick] (4.4, 0) -- (5.6, -0.4);
\draw [thick] (4.4, 0.4) -- (5.6, 0);
\draw [thick] (4.4, -0.4) -- (5.6, 0.4);

\draw [thick] (4.4, 2.5) -- (5.6, 2.1);
\draw [thick] (4.4, 2.9) -- (5.6, 2.5);
\draw [thick] (4.4, 2.1) -- (5.6, 2.9);

\draw [thick] (4.4, -2.5) -- (5.6, -2.9);
\draw [thick] (4.4, -2.1) -- (5.6, -2.5);
\draw [thick] (4.4, -2.9) -- (5.6, -2.1);

\node [fill=white] at (5, 0) {$G_I^u$};
\node [fill=white] at (5, 2.5) {$G_I^t$};
\node [fill=white] at (5, -2.5) {$G_I^v$};

\draw [fill=black] (0, 0) circle [radius=0.2cm];
\draw [fill=black] (0, 1.5) circle [radius=0.2cm];
\draw [fill=black] (0, -1.5) circle [radius=0.2cm];

\draw [fill=black] (10, 0) circle [radius=0.2cm];
\draw [fill=black] (10, 1.5) circle [radius=0.2cm];
\draw [fill=black] (10, -1.5) circle [radius=0.2cm];

\draw [ultra thick] (0, 0) -- (4.4, -0.4);
\draw [ultra thick] (0, 1.5) -- (4.4, 2.5);
\draw [ultra thick] (0, -1.5) -- (4.4, -2.1);

\draw [ultra thick] (10, 0) -- (5.6, 0.4);
\draw [ultra thick] (10, 1.5) -- (5.6, 2.1);
\draw [ultra thick] (10, -1.5) -- (5.6, -2.5);

\node [left=0.2cm] at (0, 1.5) {$a$};
\node [left=0.2cm] at (0, 0) {$b$};
\node [left=0.2cm] at (0, -1.5) {$c$};

\node [right=0.2cm] at (10, 1.5) {$x$};
\node [right=0.2cm] at (10, 0) {$y$};
\node [right=0.2cm] at (10, -1.5) {$z$};

\node [above=0.1cm, rotate=11, fill=white] at (2, 2) {$w_{(a, t)} \cdot (2 \cdot \frac{\text{diam}(G_I)}{\Delta})$};

\node [above=0.1cm, rotate=-7, fill=white] at (2, -0.2) {$w_{(b, u)} \cdot (2 \cdot \frac{\text{diam}(G_I)}{\Delta})$};

\node [above=0.1cm, rotate=-8, fill=white] at (2, -1.8) {$w_{(c, v)} \cdot (2 \cdot \frac{\text{diam}(G_I)}{\Delta})$};

\node [above=0.1cm, rotate=-8, fill=white] at (8, 1.8) {$w_{(t, x)} \cdot (2 \cdot \frac{\text{diam}(G_I)}{\Delta})$};

\node [above=0.1cm, rotate=-8, fill=white] at (8, 0.2) {$w_{(u, y)} \cdot (2 \cdot \frac{\text{diam}(G_I)}{\Delta})$};

\node [above=0.1cm, rotate=11.5, fill=white] at (8, -2) {$w_{(v, z)} \cdot (2 \cdot \frac{\text{diam}(G_I)}{\Delta})$};

\end{tikzpicture}
\end{center}
\caption{The construction of our subset distance preserver lower bound.  Only some of the paths from the first layer of the outer graph to the last layer of the outer graph are pictured here.}
\end{figure}

One step remains in the construction.
Intuitively, we hope that the pair $(c, z) \in P_O$ still has a unique shortest path, and that this shortest path enters/leaves $G_I^v$ by some pair $(q, r) \in P_I^v$, thus enforcing that the shortest $q \leadsto r$ path in $G_I^v$ must stay in the preserver.
Unfortunately, this might not be the case in the construction so far: it could be that a new shortest $c \leadsto z$ path veers off course and enters/leaves $G_I^v$ in a different way.

To solve this problem, we simply observe that any such path must correspond to a suboptimal route from $c$ to $z$ in the outer graph.
Thus, if we simply scale up the edge weights of the outer graph to be much larger than the edge weights of the inner graph, then there is a huge implicit penalty for taking this suboptimal path.
With large enough weights, the penalty becomes so high that we can show that no such alternate path is possible, and the problem is solved.
We will see in calculations that follow in the next subsection that the following scaling is sufficient: let $\Delta$ be the minimum positive difference between the lengths of any two shortest paths in $G_O$ (before any replacement occurs); we then multiply the weight of all \emph{outer} edges -- i.e. edges that are not contained in any copy $G_I^v$ -- by a factor of $2 \cdot \frac{\text{diam}(G_I)}{\Delta}$.
Note that scaling by any larger factor would work just as well.

We will call the final graph at the end of the construction $G$.
The node subset $S$ whose distances must be preserved is defined to be all nodes in the first layer of $G_O$ together with all nodes in the last layer of $G_O$.
We then have $P_O \subseteq S \times S$, so we may simply argue that this graph cannot be sparsified below a certain level without increasing a pairwise distance in $P_O$.

\subsection{Proof of Correctness}

Our graphs have $nI + 2n$ nodes, since there are $2n$ nodes in the first and last layer of $G_O$, and each of the $n$ nodes in the middle layer has been replaced with a subgraph on exactly $I$ nodes.
Our node subset $S$ then has size $2n$.
We will next argue that any subset distance preserver $H$ of $G, S$ must keep at least $\Omega(I^{2/3}n^{2/3})$ edges in \emph{each} copy of $G_I$, which totals $\Omega(I^{2/3}n^{5/3})$ edges in $H$.
Note that, if $N = \Theta(nI)$ is the number of nodes in $G$, and $s = \Theta(n)$ is the number of nodes in $S$, then this means that $H$ has $\Omega(N^{2/3}s)$ edges, which implies Theorem \ref{thm:swlb}.

First, we observe that the shortest paths for $P_O$ in the final construction $G$ have the desired structure.
\begin{lemma} \label{lem:pathstructure}
Let $(c, z) \in P_O$, and let $\{(c, v), (v, z)\}$ be the unique shortest path from $c$ to $z$ in $G_O$.
There exists a node pair $(q, r) \in P_I^v$ such that every shortest path from $c$ to $z$ in $G$ walks the edge $(c, q)$, then walks a shortest path from $q$ to $r$ in $G_I^v$, and finally walks the edge $(r, z)$.
\end{lemma}
\begin{proof}
First, by construction, there certainly \emph{exists} a $c \leadsto v$ path $Q$ in $G$ with the structure described in this lemma statement.
The length of $Q$ is at most
$$|Q| \le 2\cdot \frac{\text{diam}(G_I)}{\Delta}\left(w_{(c, v)} + w_{(v, z)}\right) + \text{diam}(G_I).$$

Now consider any path $Q'$ from $c$ to $z$ in $G$ that does \emph{not} have the form described in this lemma.
If $Q'$ walks the edge $(c, q)$, then walks a \emph{non}-shortest path in $G_I^v$ from $q$ to $r$ in $G_I^v$, then walks the edge $(r, z)$, it is obvious that $|Q'| > |Q|$ and so $Q'$ is a non-shortest path from $c$ to $z$ in $G$.
The more interesting case to consider is when $Q'$ has the following form: it starts at $c$, then walks through some inner graph $G_I^{x_1}$, then it walks to a node $y_1$ (which could be in the first or last layer of $G$), then it walks through some inner graph $G_I^{x_2}$, and so on until it finally walks through an inner graph $G_I^{x_k}$ and then walks to its destination $z$.
We may \emph{underestimate} the length of this path, ignoring the edges used by this path in any inner graph, by the following expression:
$$|Q'| \ge 2 \cdot \frac{\text{diam}(G_I)}{\Delta} \left( w_{(c, x_1)} + \sum \limits_{i=1}^{k-1} \left(w_{(x_i, y_i)} + w_{(y_i, x_{i+1})}\right) + w_{(x_k, z)} \right)$$
Note that the sub-expression
$$w_{(c, x_1)} + \sum \limits_{i=1}^{k-1} \left(w_{(x_i, y_i)} + w_{(y_i, x_{i+1})}\right) + w_{(x_k, z)}$$
describes the length of some non-shortest path from $c$ to $z$ in $G_O$.
Therefore, by definition of $\Delta$, the length of this path is at least $\Delta$ more than $\dist_{G_O}(c, z) = w_{(c, v)} + w_{(v, z)}$.
We thus have:
\begin{align*}
|Q'| &\ge 2 \cdot \frac{\text{diam}(G_I)}{\Delta} \left(w_{(c, v)} + w_{(v, z)} + \Delta \right)\\
&= 2 \cdot \frac{\text{diam}(G_I)}{\Delta} \left(w_{(c, v)} + w_{(v, z)} \right) + 2 \cdot \text{diam}(G_I)\\
& > 2 \cdot \frac{\text{diam}(G_I)}{\Delta} \left(w_{(c, v)} + w_{(v, z)} \right) + \text{diam}(G_I)\\
& \ge |Q|
\end{align*}
So $Q$ is strictly shorter than $Q'$, and $Q'$ is not a shortest path in $G$.
The lemma follows.
\end{proof}

\begin{claim} \label{clm:pathuse}
For any node pair $(q, r) \in P_I^v$ (for any $v$), there is a pair $(c, z) \in P_O$ such that every shortest path from $c$ to $z$ in $G$ includes as a subpath some shortest path from $q$ to $r$ in $G_I^v$.
\end{claim}
\begin{proof}
Let $P_O^v \subseteq P_O$ be the set of node pairs $(c, z) \in P_O$ whose unique shortest path in $G_O$ includes the node $v$.
It follows from Theorem \ref{thm:ceouter} that there are exactly $\frac{D}{2}$ such pairs in $P_O^v$.
When we replace $v$ with the inner graph $G_I^v$, we also have exactly $p_I = \frac{D}{2}$ pairs in $P_I^v$.
Thus, we create a one-to-one correspondence between the pairs in $P_O^v$ and the pairs in $P_I^v$.
In other words, for any given pair $(q, r) \in P_I^v$, there is a pair $(c, z) \in P_O^v$ such that the edges of the shortest path $\{(c, v), (v, z)\}$ in $G_O$ are replaced by edges $(c, q), (r, z)$ in $G$.
We may now apply Lemma \ref{lem:pathstructure} to conclude that every shortest path from $c$ to $z$ in $G$ includes as a subpath some shortest path from $q$ to $r$ in $G_I^v$.
\end{proof}

\begin{claim} \label{clm:inneredges}
Any distance preserver $H$ of $G, P_O$ must keep $\Omega(I^{2/3}n^{2/3})$ edges in each inner graph $G_I^v$.
\end{claim}
\begin{proof}
Suppose towards a contradiction that $H$ has $o(I^{2/3}{n^{2/3}})$ edges in some inner graph $G_I^v$.
From Theorem \ref{thm:cewlb}, there exists a node pair $(q, r) \in P_I^v$ for which \emph{no} shortest path from $q$ to $r$ in $G_I^v$ has all of its edges still in $H$.
By Claim \ref{clm:pathuse}, there is a pair $(c, z) \in P_O$ for which every shortest path from $c$ to $z$ in $G$ includes as a subpath some shortest path from $q$ to $r$ in $G_I^v$.
It follows that no shortest path from $c$ to $z$ in $G$ has all of its edges remaining in $H$.
This contradicts the fact that $H$ is a preserver of $G, P_O$, and thus, $H$ must keep $\Omega(I^{2/3}n^{2/3})$ edges in each inner graph $G_I^v$.
\end{proof}
Theorem \ref{thm:swlb} now follows from the calculations at the beginning of this subsection.

\subsection{The Unweighted Construction}

The intuition behind the construction in the unweighted setting is exactly the same as the intuition in the weighted setting.
However, a problem arises due to our inability to use edge weights: while previously we placed large edge weights on our ``outer edges'' to enforce that the shortest path topology of the graph endured over the obstacle product replacement, no such operation is possible in the unweighted setting (the natural attempt is to replace weighted edges with long paths, but this introduces too many new nodes to the graph and critically harms the lower bound).
Instead, we must use some caution in our construction to avoid changing the shortest paths of the graph over the inner graph replacement step.

The solution we employ is to simply use a layered inner graph for which all pairs $(q, r) \in P_I^v$ have $q$ in the first layer and $r$ in the last layer.
We then perform the obstacle product replacement as before, but we take care to only connect first-layer inner graph nodes to first-layer outer graph nodes, and last-layer inner graph nodes to last-layer outer graph nodes.
Intuitively, this suffices because \emph{any} $c \leadsto z$ path for a pair $(c, z) \in G_O$ must then cross a system of inner graph layers \emph{at some point} just to get from the first to the third layer of the outer graph.
Thus, we can argue that no alternate $c \leadsto z$ path can be shorter than the one that simply takes a direct route across the layers of $G_I^v$. \\

We now proceed with more formality.
We draw our outer graphs from the following theorem:
\begin{theorem} [\cite{CE06}]
There is an infinite family of $3$-layered undirected unweighted graphs $G$ with $n$ nodes per layer and
$$\Omega\left(\frac{n^2}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right)$$
edges, as well as a set $P_O$ of $p_O$ node pairs with one point in the first layer and the other point in the last layer, such that:
\begin{enumerate}
\item All nodes in the middle layer have the same even degree $D = \Theta\left(\frac{n}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right)$.
\item For all $(s, t) \in P_O$, there is a unique shortest path in $G$ from $s$ to $t$, and it includes exactly two edges.
\item For each edge in $G$, there is a unique pair in $P_O$ whose shortest path includes that edge.
\end{enumerate}
\end{theorem}

The following theorem is the analogue of Theorem \ref{thm:cewlb}:
\begin{theorem} [\cite{CE06}] \label{thm:ceuwlb}
For any $n$, for any integer $d \ge 2$, there is an undirected unweighted graph $G$ on $n$ nodes and
$$\Theta\left(n^{2d/(d^2 + 1)}p^{d(d-1)/(d^2+1)}\right)$$
edges, and a set $P$ of $p = p(n)$ node pairs such that there is a unique shortest path in $G$ between any pair in $P$, these shortest paths are edge disjoint, and the edges of $G$ are precisely the union of these paths.
\end{theorem}

However, we do \emph{not} draw our inner graphs directly from this theorem, since these graphs are not layered.
Instead, we use:
\begin{lemma} \label{lem:layeredplb}
For any $n$, for any integer $d \ge 2$, there is an undirected unweighted graph $G$ on $n$ nodes and
$$\Theta\left(n^{2d/(d+1)^2}p^{d/(d+1)}\right)$$
edges, and a set $P$ of $p = p(n)$ node pairs such that there is a unique shortest path in $G$ between any pair in $P$, these shortest paths are edge disjoint, and the edges of $G$ are precisely the union of these paths.
\textbf{Moreover,} there is an integer $\ell = \ell(n)$ such that $G$ is a graph on $\ell$ layers and for each pair $(q, r) \in P$, we have $q$ in the first layer, $r$ in the last layer, and $\dist_G(q, r) = \ell - 1$.
\end{lemma}
\begin{proof}
Start with a graph $G$ and pair set $P$ from Theorem \ref{thm:ceuwlb} with $n$ nodes and $p$ pairs.
We modify $G, P$ in two steps to produce a graph satisfying this lemma.

\paragraph{Regularizing $P$.}

First, we will slightly modify the pair set $P$ such that all pairs have exactly the same distance in $G$.
Let $L$ be the average distance between a pair in $P$.
Since our pairs have unique edge-disjoint shortest paths, note that there are exactly $pL$ edges in $G$.
For each pair $(q, r) \in P$, we remove $(q, r)$ from $P$, we divide the shortest path from $q$ to $r$ into subpaths of length exactly $\lfloor L/2 \rfloor$, and we add the endpoints of each of these subpaths back to $P$ as a new pair.
If there is a shorter ``remainder'' subpath of length less than $\lfloor L/2 \rfloor$ left over at the end, we remove all edges in this subpath from $G$ (and we do \emph{not} add its endpoints back to $P$).
It is clear that all pairs in $P$ now have the same distance $\lfloor L/2 \rfloor$ between them.
Further, the shortest paths in the new $P$ are still unique and edge-disjoint, and $G$ is precisely the union of these paths.
We have removed at most $p \cdot (\lfloor L/2 \rfloor - 1)$ edges from $G$; since $G$ originally had $p \cdot L$ edges, a constant fraction of the edges in $G$ remain.
Finally, since each pair in $P$ has distance exactly $\lfloor L/2 \rfloor$, and since each pair in $P$ has a unique edge-disjoint shortest path in $G$ between its endpoints, the total number of pairs in the new $P$ must still be $\Theta(p)$.
Thus, we have changed the size of $P$ and the density of $G$ only by constant factors throughout this process.

\paragraph{Layering $G$.}

Next, we make $\ell := \lfloor L/2 \rfloor + 1$ copies of $G$, and for each edge $(u, v)$ in the original graph, we add an edge between the copy of $u$ in layer $i$ and the copy of $v$ in layer $i+1$ (for all $1 \le i \le \lfloor L/2 \rfloor$; we also add edges from the copy of $v$ in layer $i$ to the copy of $u$ in layer $i+1$).
We replace each pair $(q, r) \in P$ with the pair $(q_1, r_{\lfloor L/2 \rfloor+1})$, where $q_1$ is the copy of $q$ in the first layer and $r_{\lfloor L/2 \rfloor+1}$ is the copy of $r$ in the last layer.
Note that the total number of pairs does not change in this process.
Also note that, by construction, since the original shortest paths were unique and edge-disjoint, the shortest paths for the pairs $(q_1, r_{\lfloor L/2 \rfloor+1})$ are still unique and edge-disjoint.
Additionally, these paths have length exactly $\lfloor L/2 \rfloor = \ell - 1$, as claimed.

\paragraph{Analysis.}

The graph $G$ is now a layered graph on $\Theta(nL)$ nodes, as well as $\Theta(p)$ node pairs, and for each node pair there is a unique edge disjoint shortest path of length $\Theta(L)$ between its endpoints.
Thus, any preserver of $G, P$ must have $\Theta(pL)$ edges in it.
Recall that $pL$ is precisely equal to the number of edges originally in $G$.
We may thus compute:
$$L = \frac{|E(G)|}{p} = \Theta(n^{2d/(d^2 + 1)}p^{d(d-1)/(d^2+1) - 1}) = \Theta(n^{2d/(d^2 + 1)}p^{(-d-1)/(d^2+1)})$$
The number of edges in any preserver of $G, P$ is then
$$\Theta(pL) = \Theta\left(n^{2d/(d^2 + 1)}p^{d(d-1)/(d^2+1)}\right) = \Theta\left((nL)^{2d/(d+1)^2} p^{d/(d+1)}\right)$$
and the lemma is complete.
\end{proof}

We draw the inner graphs in our construction from Lemma \ref{lem:layeredplb}.
We then perform our replacement product as before, with the following essential detail discussed earlier:
Given a shortest path $\{(c, v), (v, z)\}$ in $G_O$, when we replace $v$ with $G_I^v$ and choose a corresponding pair $(q, r) \in P_I^v$, we add edges $(c, q)$ and $(r, z)$ to our new graph \emph{where $c, q$ are in the first layers of $G_O, G_I^v$ (respectively) and $z, r$ are in the last layers of $G_O, G_I^v$ (respectively)}.

The fact that we use layered inner graphs in this way allows us to re-prove Lemma \ref{lem:pathstructure} using a slightly modified argument:
\begin{proof} [Proof of Lemma \ref{lem:pathstructure} in the unweighted construction]
As in the weighted construction, for some pair $(c, z) \in P_O$, let $Q$ be a path from $c$ to $z$ in $G$ that walks the edge $(c, q)$, then walks a shortest path from $q$ to $r$ in $G_I^v$, and finally walks the edge $(r, z)$.
The length of this path is precisely $|Q| = 1 + (\ell - 1) + 1 = \ell + 1$,
where $\ell$ is the number of layers in $G_I$.
Now, consider any alternate path $Q'$ from $c$ to $z$ in $G$.
Note that all paths from $c$ to $z$ must include a path from the first layer of some copy of $G_I$ to the last layer of that copy, in order to reach $z$ in the last layer of $G_O$.
This portion of the path has length $\ell - 1$.
If $Q'$ is as short as $Q$, i.e. $|Q'| \le 1 + \ell$, then $Q'$ may contain at most two other edges.
In particular, these must be the first (incident on $c$) and last (incident on $z$) edge of the path, which are not contained in any copy of $G_I$.

Note that there is a unique path of length $2$ from $c$ to $z$ in $G_O$, which uses the node $v$ as its midpoint.
Thus, the first (resp. last) edge in $Q'$ necessarily connects $c$ (resp. $z$) to nodes in $G_I^v$.
By construction, the only edges in $G$ that do so are $(c, q)$ and $(r, z)$.
Thus, any shortest path from $c$ to $z$ in $G$ has the form described in Lemma \ref{lem:pathstructure}: it walks the edge $(c, q)$, then it walks a shortest path from $q$ to $r$ in $G_I^v$, and finally it walks the edge $(r, z)$.
\end{proof}

We may then prove Claim \ref{clm:pathuse} via an identical proof to the one used in the weighted setting.
Finally, we have this analogue of Claim \ref{clm:inneredges}:
\begin{claim}
Any distance preserver $H$ of $G, P_O$ must keep
$$\Omega \left(I^{2d/(d^2+1)} \left(\frac{n}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right)^{d(d-1)/(d^2+1)} \right)$$
edges in each inner graph $G_I^v$.
\end{claim}
\begin{proof}
Identical to the proof of Claim \ref{clm:inneredges}.
\end{proof}

Thus, we have a graph on $\Theta(nI)$ nodes, a set $S$ of $s = \Theta(n)$ nodes (the first layer together with the last layer of $G$), and any preserver of $G, S$ contains a preserver of $G, P_O$ and thus has
\begin{align*}
&\Omega \left(I^{2d/(d^2+1)} n^{1 + d(d-1)/(d^2+1)} \left(\frac{1}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right)^{d(d-1)/(d^2+1)} \right)\\
= \, &\Omega \left(I^{2d/(d^2+1)} n^{1 + d(d-1)/(d^2+1)} \left(\frac{1}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right) \right)
\end{align*}
edges.
We may rephrase this edge bound as
\begin{align*}
\Omega\left((nI)^{2d/(d^2+1)} s^{(2d-1)(d-1)/(d^2+1)}\left(\frac{1}{2^{\Theta(\sqrt{\log n \cdot \log \log n})}}\right)\right)
\end{align*}
and since $G$ has $\Theta(nI)$ nodes, this implies Theorem \ref{thm:sulb}.

\section{Acknowledgements}

I am grateful to Amir Abboud for many useful discussions that have led to some of the central ideas in this paper.
I am grateful to Noga Alon for suggesting some of the connections between distance compression and combinatoric graph theory covered by Theorem \ref{thm:uupairwiseub}.
I thank my advisor Virginia Vassilevska Williams for advice and technical discussions.
Finally, I thank an anonymous reviewer for many very helpful comments and corrections that have greatly improved the current presentation of this work.

redpajama_set_name: RedPajamaArXiv


Astoresque is an original new composition for the classical guitar. It's an homage to Astor Piazzolla, the great Argentinian composer. His music remains as full of fire and spirit as the moment it was written.
Piazzolla was a virtuoso of the bandoneón, an accordion-like instrument pictured above, but this piece is for guitar, which I feel suits the mood and mode of expression very well. Piazzolla's original compositions and arrangements for guitar are usually very demanding to play, and some are extremely difficult: in contrast, Astoresque is more manageable, if not altogether easy.
I hope you enjoy listening to and playing this piece!
Here's a preview the first page of the composition. Click to view larger!
Soon, it's all going to be FREE!


A garden that I designed for the landscape contractors Artscape, has won the Overall Design and Build Award in the Association of Professional Landscape Awards 2010. See the Barn Garden in my portfolio and also Artscape.
Time to smash up the concrete!


Apparently, you have better odds off surviving in the sea with sharks than in a river with just one croc. Perhaps, that is why there are tours where you can get up close and personal with sharks within the safety of a shark cage (which sometimes may not be as safe as one thought) and not up close and personal croc tours. Oh, wait. Actually there is! As it turns out, you can get up close with crocodile too and the place where you can put yourself in a heart-pounding situation is Cage of Death at Australia's Crocosaurus Cove, located in Darwin City.
Obviously, when facing a reptile that has a potential bite force of over 3,000 pound per square inch, a shark cage is not going to cut it (because it will probably cut through the metal like hot knife through butter, duh). So, no. Cage of Death is not actually a cage; instead, it is a transparent glass tube. Good thing. Cos' getting up close with this salt water variant of the ultimate killing machine does not justify losing a limb or two. As you can see from the images, you will be immersed in water as the tube dip right smack into the middle of the croc's playground.
From there, you will get 15 minutes of bonding time with the 5-meter-plus long prehistoric creature that is probably wondering how to make a meal out of you. But, not too worry. You are safe within the glass tube confine, plus it is fed regularly, so it is not hungry for anything that moves (probably) and also, you'd be able to check out its dinning etiquette. The tube can hold up to two person with room to spare, and so, if you need a company to stare death right in the eyes, you can.
Be warned though, it is not cheap. The Cage of Death experience, which is part of the full reptile themed pack, commands a hefty 170 Australian dollars (roughly US$130) per person. On top of that, the experience is limited to 11 sessions per day and therefore, if you want to have a go, be sure check the availability and book the ticket(s) in advance.


As I write this introductory paragraph, I haven't locked down the title of today's narrative. The reasoning is simple: like a blind man wandering in the forest, there's no designated direction, but I surely will have bumped into some terrific ideas, or small forest animals, by the end of my writing session.
Sure, I have a generalized idea, but no set-in-stone-must-have-narrative, at this specific moment. The problem is sorting and cataloging all of the potential holiday-based stories, in the most logical sense, that need to be told over the next month.
The first of December marks the beginning of the holiday season as our American culture officially institutes the Twenty-five Days of Christmas countdown. Children all around the nation, and many adults just like me, are giddy with excitement. There is an anticipation of something, in the air from the West Coast to the East Coast, as we roll toward Christmas morning.
I say something because, in today's complex culture, it seems that every family has a different focus on the festivities of December, whether rooted in the traditions of faith, fantasy, or commercialism. Some parents subscribe to the celebration of Jesus's birth, while other parents boldly sell the mythology of Santa and Christmas traditions to their children—I'd like to think that our family consists of a fair mixture of both. My wife and I have developed our own collection of traditions that we intend to pass along to our own children. As such, it's my intention to pepper several daily slots of December's story-telling with tales from my own family and the traditions, both faith-based and secular, that we employ from year to year.
In our house, the holiday season always begins with the Christmas tree, in conjunction with Black Friday shopping on the day following Thanksgiving. The normal tradition follows a "we will stay at home and decorate the tree while mom goes shopping" pattern.
The roster for that day includes moving all of the living room furniture, sweeping under the Never Ever Gets Cleaned areas, vacuuming the carpets and hardwood floors, and selecting a spot for the tree. This cleaning ritual is what I learned from my father, for this time each year he surprised everyone with his innate ability to thoroughly clean, although it was a skill that seemed sadly misplaced for the remaining months of the year.
The memories are burned into my mind, and each Christmas I recall, with extreme fondness, my parents' Christmas traditions. Mom would always play her favorite vinyl album on the record player while we moved, and cleaned, and swept, and cleaned some more: Merry Christmas by Johnny Mathis. She would also hang a red Advent calendar on the kitchen wall, decorated with hard candy, fastened to felt by green yarn, one piece for each kid and each day of the month until Christmas morning. Dad would resurrect the plywood platform, usually from the damp basement, and then setup a suitable tiny village (featuring the plastic Kentucky Fried Chicken restaurant), slot car racetrack, or HO model train configuration—as an adult, I followed the same tradition for years, until the kids failed to express a continued interest in the entire miniature world process. Finally, I just remembered the idea of do-it-yourself garland: my mother would make a few batches of homemade popcorn, threading the treat on string, and we would make our own strands of decorative goodness for the Christmas tree. Those were magical years, for me.
Snapping back from my stroll down Nostalgia Lane: currently on the television, The Polar Express (2004) is playing in its entirety, which is one of our family's favorite holiday movies, and my kids are opting to watch the show rather than clean the dust bunnies—typical behavior.
Logically, the next step involves finding the Christmas tree in the garage, and finally assembling the beast. The king of the living room is our sectional leather couch, and it is that piece of furniture that dictates the available options for tree placement. In front of the dog painting? Lodged in the back corner behind the couch? Placed in front of the large glass window facing the street? Those are the only options, and, upon a family vote, the latter choice is the clear winner by majority vote. Despite our best tree-raising intentions, our Tree-Decorating ceremony was delayed, due to some faulty bulbs in the pre-lit tree—the unlit tower of plastic was sorrowfully assembled in our home, then promptly abandoned.
And we return to the project, one week later, to fully decorate the tree with ribbon, bulbs, ornaments, and candy canes. With the burned-out string replaced by a fresh line-up of brightly lit bulbs, I dragged the boxes of Christmas decorations from the garage. The first layer is always a swirl of red glitter ribbon wrapped around the tree. Following the ribbon, the generic glass bulbs are added to the tree. We have a collection of thirty-six deep red bulbs—well, years later, it's more like twenty-two—in three different sizes: small, medium, and large. Once those bulbs have been added (large ones lower toward the base, smaller perched near the top half), the unique ornaments are examined.
To be perfectly honest, we have too many ornaments; they seem to reproduce by themselves—probably undisturbed in the dark garage—from year to year. Not only do each of the children have their own set of ornaments, collected from each year of their lives, my wife and I curate our own boxes of ornaments from childhood. Additionally, my oldest brother has a tradition of his own, where he mails holiday ornaments each year, usually selections from his Disney employer.
Like I said, too many. From one year to next, we need to rotate the selected ornaments for the upcoming season. With the bounty laid out before them, the children choose which ornaments or bulbs or crafty doodads that will get added to the tree. Most of the kids participate, without complaint, but my wife chooses to "sit this one out", claiming the following mantra of that's kind of your thing, Dollface. No worries, I'm used to it by now.
To finish the tree, we conduct another family vote to decide the tree-topper decoration: silver star, red ribbon bow, or angel with lace dress. This is the year of the lace angel, and she proudly tops the finished tree. Lastly, a box of candy canes are unwrapped and individually hung from random branches.
The tree is finally finished, and (as always) is lovely. For our family, the Christmas tree is a big deal, and an integral component of Christmas. I'm a little sad that our process was delayed by a week, but there's not much I could do about that, with dead lights and our busy family schedule during the school week. We light the tree every day during December and it's the focal point of our living room, serving as a reminder to Christ's birth, which is our reason for the season, and what our family anticipates during this time of the year.
With the fully assembled tree glowing in the darkened living room, perched in front of the window facing the street, reflected in the television glass, my wife is pleased with the final product—even though she sat in the leather recliner and watched the entire process, under a warm blanket, while holding the dog, without helping.
"When are we going to work on the lights in the front yard?", she asks.
"Don't you remember? I do the inside, you do the outside…", I reply.
That's kind of your thing, Dollface.


Life Management Services: No problem?
Some of you who read last week's blog have raised thoughtful questions about forgiveness and the function of forgiveness in relationships. "Instant forgiveness", as I phrased it, does not serve the persons or the relationship well. What then makes forgiveness an authentic and healing response?
Relational issues around forgiveness are not easy to sort out. For one reason, the significance we assign forgiveness sometimes reflects an unconscious sense of entitlement. In life or relationships if we believe that we are entitled to pain free experience, we are likely to find ourselves struggling to forgive most people and most things (including the weather) most of the time. Life, as Scott Peck wrote, is difficult. Consequently, if we believe that whoever or whatever causes us any discomfort at any time should be forgiven, then the instructions Jesus gave (forgive seventy times seven) seriously understates the size of our daily forgiveness task.
Most of us understand that such an approach trivializes forgiveness into semantic nonsense. Most of us also understand intuitively that authentic forgiveness processes cannot be generalized into a "one-size-fits-all" response. When and why then, we ask ourselves, should we forgive? And, equally difficult, what are the crucial defining factors that mark authentic healing acts of forgiveness?
In blogs to come, we'll consider these tough issues in the context of effective relationship skills.
I observed an incident this last week that provides a useful beginning point.
By bad planning and worse management, I found myself in a busy supermarket at one of the busiest times in the day. Tired people were struggling with market baskets and tired hungry children while attempting to navigate around each other and the end of aisle displays that offered the sales of the week.
One frail white-haired woman while seeking to avoid another customer turned her cart sharply and caught the edge of a display of cans of tuna fish. As the cans began cascading down into the aisle, the woman backed up in dismay and bumped into a display of breakfast food boxes that obligingly began to join the tuna fish on the floor. By the time a store employee reached the disaster area, the woman was trembling and her eyes were filled with tears.
The young man calmly surveyed the chaos, then turned to her and smiled.
Was forgiveness the point here? How does your sense of forgiveness lead you to understand this story?
Thinking with you about both the self-knowledge and social skill necessary to distinguish between "no problem" and injury for which forgiveness is the only way to relational growth.