2026-07-21T11:54:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21082 2024-09-23T09:13:16Z ddc:004 open_access

How to Reduce Temporal Cliques to Find Sparse Spanners Angrick, Sebastian Bals, Ben Friedrich, Tobias Gawendowicz, Hans Hastrich, Niko Klodt, Nicolas Lenzner, Pascal Schmidt, Jonas Skretas, George Wells, Armin Temporal Graphs temporal Clique temporal Spanner Reachability Graph Connectivity Graph Sparsification Many real-world networks, such as transportation or trade networks, are dynamic in the sense that the edge-set may change over time, but these changes are known in advance. This behavior is captured by the temporal graphs model, which has recently become a trending topic in theoretical computer science. A core open problem in the field is to prove the existence of linear-size temporal spanners in temporal cliques, i.e., sparse subgraphs of complete temporal graphs that ensure all-pairs reachability via temporal paths. So far, the best known result is the existence of temporal spanners with 𝒪(nlog n) many edges. We present significant progress towards proving whether linear-size temporal spanners exist in all temporal cliques. We adapt techniques used in previous works and heavily expand and generalize them. This allows us to show that the existence of a linear spanner in cliques and bi-cliques is equivalent and using this, we provide a simpler and more intuitive proof of the 𝒪(nlog n) bound by giving an efficient algorithm for finding linearithmic spanners. Moreover, we use our novel and efficiently computable approach to show that a large class of temporal cliques, called edge-pivotable graphs, admit linear-size temporal spanners. To contrast this, we investigate other classes of temporal cliques that do not belong to the class of edge-pivotable graphs. We introduce two such graph classes and we develop novel algorithmic techniques for establishing the existence of linear temporal spanners in these graph classes as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sebastian Angrick and Ben Bals and Tobias Friedrich and Hans Gawendowicz and Niko Hastrich and Nicolas Klodt and Pascal Lenzner and Jonas Schmidt and George Skretas and Armin Wells 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.11 urn:nbn:de:0030-drops-210822 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.11 eng https://creativecommons.org/licenses/by/4.0/legalcode