2017/08/10 by Kshitij Gajjar, Gajjar, Kshitij, Jaikumar Radhakrishnan +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1708.03081
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 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 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 Ω(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 Ω(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 Ω(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ïve 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.