Abstract: Computing and maintaining shortest paths is a fundamental problem in computer science. We consider two ways of succinctly representing shortest paths in graphs: (i) distance-preserving subgraphs, and (ii) parametric shortest paths. In this talk, we will survey our results on these topics. In particular, we will present the following two results in detail.
(i) Given a graph with $k$ special vertices (called terminals), a distance-preserving subgraph of it is a subgraph which has the same pairwise distances between the terminals as in the original graph. We prove that every interval graph with $k$ terminals has a distance-preserving subgraph with $O(k \log k)$ vertices of degree three or more. We also prove that this bound is tight.
(ii) Given a graph with two special vertices $s$ and $t$, and edge weights that vary linearly with a parameter $\lambda$, the parametric shortest path complexity of the graph is the number of times the shortest $s$-$t$ path changes as $\lambda$ varies from $-\infty$ to $+\infty$. We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices, such that the parametric shortest path complexity of $G_n$ is $n^{\Omega(\log n)}$. This refutes a conjecture of Nikolova (2009).
