Distance-preserving subgraphs of interval graphs

DOI10.4230/LIPICS.ESA.2017.39zbMATH Open1442.05140arXiv1708.03081OpenAlexW2963209922MaRDI QIDQ5111726FDOQ5111726

Authors: Kshitij Gajjar, Jaikumar Radhakrishnan 

Publication date: 27 May 2020

Abstract: 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 $G_{mathrmint}$ 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_{mathrmint}$ has $Omega(klogk)$ branching vertices. Furthermore, we prove that every interval graph admits a distance-preserving subgraph with $O(klogk)$ branching vertices, implying that the $Omega(klogk)$ 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(klogk)$ 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_{mathrmint}$ is constructed using bit-reversal permutation matrices. The $O(klogk)$ 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.

Full work available at URL: https://arxiv.org/abs/1708.03081

Recommendations

• Sparse Distance Preservers and Additive Spanners
• scientific article; zbMATH DE number 1161357
• scientific article; zbMATH DE number 2079365
• Linear size distance preservers
• Graph-Theoretic Concepts in Computer Science

zbMATH Keywords

interval graphsshortest pathbit-reversal permutation matrixdistance-preserving subgraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• An Algorithm for the Machine Calculation of Complex Fourier Series
• Electing a leader in a synchronous ring
• Graph spanners
• Sparse Sourcewise and Pairwise Distance Preservers
• Clique partitions, graph compression and speeding-up algorithms
• Steiner points in tree metrics don't (really) help
• Logarithmic Lower Bounds in the Cell-Probe Model
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
• Preserving Terminal Distances Using Minors
• Distance-Preserving Graph Contractions

Cited In (10)

• Title not available (Why is that?)
• Graph spanners: a tutorial review
• Distance-Preserving Graph Contractions
• Distance-Preserving Graph Contractions
• New Results on Linear Size Distance Preservers
• Reconfiguring shortest paths in graphs
• Realizing Interval Graphs with Size and Distance Constraints
• Title not available (Why is that?)
• Improved Guarantees for Vertex Sparsification in Planar Graphs
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms

This page was built for publication: Distance-preserving subgraphs of interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111726)