2026-07-21T02:34:26Z https://drops.dagstuhl.de/oai

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

Temporal Dominating Set and Temporal Vertex Cover Under the Lense of Degree Restrictions Herrmann, Anton Komusiewicz, Christian Morawietz, Nils Sommer, Frank NP-hard problem FPT-algorithm Treewidth Color coding We study the Temporal Dominating Set problem, in which one asks whether a temporal graph 𝒢 = (G₁,… , G_T) given as a sequence of snapshot graphs, over the same vertex set V, has a set S of temporal vertices of size at most k such that each vertex v of V is dominated by some w ∈ S in the snapshot that contains w. Additionally, we consider Temporal Partial Dominating Set, where one asks whether at least t (and not necessarily all) vertices of V can be dominated by S and a further generalization in which the solution may only contain a bounded number of temporal vertices from each snapshot. We analyze how the complexity of Temporal (Partial) Dominating Set is influenced by the maximum snapshot degree and the structure of the underlying graph, the graph with vertex set V and whose edge set is the union of all snapshot edge sets. For example, we obtain a complexity dichotomy for the maximum snapshot degree and we show that Temporal Partial Dominating Set is fixed-parameter tractable for tw+Δ, where tw and Δ denote the treewidth and the maximum degree of the underlying graph of 𝒢, respectively. We also show which of our results transfer to the well-studied Temporal Vertex Cover problem. For example, we show that Temporal Vertex Cover is also fixed-parameter tractable for tw+Δ which substantially extends the previously known polynomial-time algorithms for the case that the underlying graph is a path or cycle. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anton Herrmann and Christian Komusiewicz and Nils Morawietz and Frank Sommer 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.16 urn:nbn:de:0030-drops-230695 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode