Distance-preserving Subgraphs of Interval Graphs

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 mathsfNP-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 Gint 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 Gint has Omega(klog k) branching vertices. Furthermore, we prove that every interval graph admits a distance-preserving subgraph with O(klog k) branching vertices, implying that the Omega(klog 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(klog 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. Gint is constructed using bit-reversal permutation matrices. The O(klog 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.