2026-07-21T23:33:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2883 2024-03-06T10:33:40Z ddc:004 open_access

Finding Sparser Directed Spanners Berman, Piotr Raskhodnikova, Sofya Ruan, Ge Approximation algorithms directed graphs spanners A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, a subgraph $H = (V,E_H)$ is a $k$-spanner of a graph $G=(V,E)$ if for every pair of vertices $u,v \in V$, the shortest path distance $dist_H(u,v)$ from $u$ to $v$ in $H$ is at most $k.dist_G(u,v)$. We focus on spanners of directed graphs and a related notion of transitive-closure spanners. The latter captures the idea that a spanner should have a small diameter but preserve the connectivity of the original graph. We study the computational problem of finding the sparsest $k$-spanner (resp., $k$-TC-spanner) of a given directed graph, which we refer to as DIRECTED $k$-SPANNER (resp., $k$-TC-SPANNER). We improve all known approximation algorithms for these problems for $k\geq 3$. (For $k=2$, the current ratios are tight, assuming P$\neq$NP.) Along the way, we prove several structural results about the size of the sparsest spanners of directed graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Piotr Berman and Sofya Raskhodnikova and Ge Ruan 2010 Is Part Of LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2010.424 urn:nbn:de:0030-drops-28830 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.424 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode