2026-07-21T23:47:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23062 2025-10-02T12:32:42Z ddc:004 open_access

Spanner Enumeration for Temporal Graphs Kurita, Kazuhiro Marino, Andrea Schoeters, Jason Uno, Takeaki temporal graphs temporal spanners one-to-all connectivity all-to-all connectivity enumeration NP-completeness Dual-hardness binary partition tree flashlight search polynomial delay A spanner of a temporal graph is a subset of edges that preserves connectivity over time between vertices. A minimal spanner is one in which no additional edges can be removed without breaking this connectivity. Our focus is on enumerating minimal spanners for a given temporal graph. We explore several variations of this problem based on the type of connectivity that must be maintained, ranging from one-to-all connectivity to one-to-all-to-one, many-to-all, and finally all-to-all connectivity. We establish that these problems become progressively harder: (i) We present a polynomial-delay enumeration algorithm for one-to-all connectivity; (ii) We prove Dual-hardness for both one-to-all-to-one and many-to-all connectivity, even in the restricted case of two-to-all; (iii) Finally, for all-to-all connectivity, we show that enumeration cannot be performed in output-polynomial time unless P = NP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kazuhiro Kurita and Andrea Marino and Jason Schoeters and Takeaki Uno 2025 Is Part Of LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2025.9 urn:nbn:de:0030-drops-230621 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode