Minimizing Branching Vertices in Distance-Preserving Subgraphs.

It is \(\textsf {NP}\)-hard to determine the minimum number of branching vertices needed in a single-source distance-preserving subgraph of an undirected graph. We show that this problem can be solved in polynomial time if the input graph is an interval graph.