Abstract: Given a graph $G$ with one source vertex $s$ and several target vertices, a shortest path tree rooted at $s$ is a subgraph of $G$ that preserves distances from $s$ to each of the target vertices. A shortest path tree is called optimal if it has the minimum number of branching vertices (vertices of degree three or more). In this talk, we will see proofs of the following results.
1. Finding an optimal shortest path tree is $\mathsf{NP}$-hard for general graphs.
2. Finding an optimal shortest path tree is in $\mathsf{P}$ for interval graphs.
This is based on joint work with Jaikumar. A condensed version of this talk will be given at CSR 2019 in Novosibirsk, Russia.
