We explore the parameterized complexity of Bounded Density Vertex Deletion (BDVD): given a graph G, an integer budget k, and a target density τ_ρ, the task is to determine whether the density (i.e. number of edges divided by number of vertices) of the densest subgraph of G can be reduced to at most τ_ρ by deleting at most k vertices. Our primary focus is on structural graph parameters related to treewidth, as the parameterized complexity of BDVD with respect to treewidth was left as open question by Bazgan et al. [JCSS, 2025]. We resolve this question by showing W[1]-hardness with respect to various parameters, including treedepth and feedback vertex number. These results imply W[1]-hardness with respect to treewidth. We obtain positive results for parameters larger than treedepth and feedback vertex number, namely we show BDVD is in FPT parameterized by the max leaf number or vertex integrity. Under the assumption that the target density τ_ρ is a fixed constant the parameterized complexity landscape of BDVD changes drastically, allowing a fixed-parameter tractable algorithm even for parameters smaller than treewidth, namely cliquewidth. Altogether, our results provide a refined complexity landscape for Bounded Density Vertex Deletion, sharply distinguishing between tractable and intractable parameter regimes under structural parameterizations.

We study the Temporal Dominating Set problem, in which one asks whether a temporal graph G = ( G 1 , ⋯ , G T ) given as a sequence of snapshot graphs over the same vertex set V has a set S of at most k temporal vertices 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 whose edge set is the union of all snapshot edge sets. For example, we obtain a complexity dichotomy for the maximum snapshot degree and 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 G , respectively. We also study 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.

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.