DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2025.12

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set

Authors: Anton Herrmann, Christian Komusiewicz, Nils Morawietz, and Frank Sommer

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract

A temporal graph is a finite sequence of graphs, called snapshots, over the same vertex set. Many temporal graph problems turn out to be much more difficult than their static counterparts. One such problem is Timeline Vertex Cover (also known as MinTimeline_∞), a temporal analogue to the classical Vertex Cover problem. In this problem, one is given a temporal graph 𝒢 and two integers k and 𝓁, and the goal is to cover each edge of each snapshot by selecting for each vertex at most k activity intervals of length at most 𝓁 each. Here, an edge uv in the ith snapshot is covered, if an activity interval of u or v is active at time i. In this work, we continue the algorithmic study of Timeline Vertex Cover and introduce the Timeline Dominating Set problem where we want to dominate all vertices in each snapshot by the selected activity intervals. We analyze both problems from a classical and parameterized point of view and also consider partial problem versions, where the goal is to cover (dominate) at least t edges (vertices) of the snapshots. With respect to the parameterized complexity, we consider the temporal graph parameters vertex-interval-membership-width (vimw) and interval-membership-width (imw). We show that all considered problems admit FPT-algorithms when parameterized by vimw+k+𝓁. This provides a smaller parameter combination than the ones used for previously known FPT-algorithms for Timeline Vertex Cover. Surprisingly, for imw+k+𝓁, Timeline Dominating Set turns out to be easier than Timeline Vertex Cover, by also admitting an FPT-algorithm, whereas the vertex cover version is NP-hard even if imw+k+𝓁 is constant. We also consider parameterization by combinations of n, the vertex set size, with k or 𝓁 and parameterization by t. Here, we show for example that both partial problems are fixed-parameter tractable for t which significantly improves and generalizes a previous result for a special case of Partial Timeline Vertex Cover with k = 1.

Cite as

Anton Herrmann, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{herrmann_et_al:LIPIcs.IPEC.2025.12,
  author =	{Herrmann, Anton and Komusiewicz, Christian and Morawietz, Nils and Sommer, Frank},
  title =	{{Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.12},
  URN =		{urn:nbn:de:0030-drops-251446},
  doi =		{10.4230/LIPIcs.IPEC.2025.12},
  annote =	{Keywords: NP-hard problem, FPT-algorithm, interval-membership-width, Color coding}
}

Document

DOI: 10.4230/LIPIcs.SAND.2025.16

Temporal Dominating Set and Temporal Vertex Cover Under the Lense of Degree Restrictions

Authors: Anton Herrmann, Christian Komusiewicz, Nils Morawietz, and Frank Sommer

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract

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.

Cite as

Anton Herrmann, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. Temporal Dominating Set and Temporal Vertex Cover Under the Lense of Degree Restrictions. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{herrmann_et_al:LIPIcs.SAND.2025.16,
  author =	{Herrmann, Anton and Komusiewicz, Christian and Morawietz, Nils and Sommer, Frank},
  title =	{{Temporal Dominating Set and Temporal Vertex Cover Under the Lense of Degree Restrictions}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.16},
  URN =		{urn:nbn:de:0030-drops-230695},
  doi =		{10.4230/LIPIcs.SAND.2025.16},
  annote =	{Keywords: NP-hard problem, FPT-algorithm, Treewidth, Color coding}
}

Search Results

Documents authored by Herrmann, Anton

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set

Abstract

Cite as

Temporal Dominating Set and Temporal Vertex Cover Under the Lense of Degree Restrictions

Abstract

Cite as

Thanks for your feedback!

Could not send message