We consider the problem of finding small distance-preserving subgraphs of undirected, unweighted interval graphs with $k$ terminal vertices. To start with, we show that finding an optimal distance-preserving subgraph is $\mathsf{NP}$-hard for general graphs. Then, we show that every interval graph admits a subgraph with $O(k)$ branching vertices that approximates pairwise terminal distances up to an additive term of $+1$. We also present an interval graph $G_{\mathrm{int}}$ for which the $+1$ approximation is necessary to obtain the $O(k)$ upper bound on the number of branching vertices. In particular, any distance-preserving subgraph of $G_{\mathrm{int}}$ has $\Omega(k\log k)$ branching vertices. Furthermore, we prove that every interval graph admits a distance-preserving subgraph with $O(k\log k)$ branching vertices, implying that the $\Omega(k\log k)$ lower bound for interval graphs is tight. To conclude, we show that there exists an interval graph such that every optimal distance-preserving subgraph of it has $O(k)$ branching vertices and $\Omega(k\log k)$ branching edges, thereby providing a separation between branching vertices and branching edges. The $O(k)$ bound for distance-approximating subgraphs follows from a na\"ive analysis of shortest paths in interval graphs. $G_{\mathrm{int}}$ is constructed using bit-reversal permutation matrices. The $O(k\log k)$ bound for distance-preserving subgraphs uses a divide-and-conquer approach. Finally, the separation between branching vertices and branching edges employs Hansel's lemma for graph covering.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok