2026-07-21T20:02:47Z https://drops.dagstuhl.de/oai

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

Matching and Edge Cover in Temporal Graphs Cioni, Lapo Dondi, Riccardo Marino, Andrea Schoeters, Jason Silva, Ana graphs temporal graphs edge cover matching parameterized algorithm approximation algorithm Temporal graphs are a special class of graphs for which a temporal component is added to edges, that is, each edge possesses a set of times at which it is available and can be traversed. Many classical problems on graphs can be translated to temporal graphs, and the results may differ. In this paper, we define the {Temporal Edge Cover} and {Temporal Matching} problems and show that they are NP-complete even when fixing the lifetime or when the underlying graph is a tree. We then describe two FPT algorithms, with parameters lifetime and treewidth, that solve the two problems. We also find lower bounds for the approximation of the two problems and give two approximation algorithms which match these bounds. Finally, we discuss the differences between the problems in the temporal and the static framework. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lapo Cioni and Riccardo Dondi and Andrea Marino and Jason Schoeters and Ana Silva 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.8 urn:nbn:de:0030-drops-230614 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode