Distance-preserving subgraphs of interval graphs

DOI10.4230/LIPICS.ESA.2017.39MaRDI QIDQ5111726zbMATH OpenOpenAlexFDO

Authors Kshitij Gajjar, Jaikumar Radhakrishnan

Publication date 27 May 2020

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

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)

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.

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

Cites work

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

Cited in

(12)

• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Reconfiguring shortest paths in graphs
• scientific article; zbMATH DE number 5016709 (Why is no real title available?)
• scientific article; zbMATH DE number 19192 (Why is no real title available?)
• Preliminary results on distance-preserving graphs
• Realizing Interval Graphs with Size and Distance Constraints
• Improved guarantees for vertex sparsification in planar graphs
• Graph spanners: a tutorial review
• New results on linear size distance preservers
• On constructing regular distance-preserving graphs
• Distance-Preserving Graph Contractions
• Distance-Preserving Graph Contractions

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)