The parameterised complexity of generalised temporal domination on temporal graphs with modular structure

Jessica Enright; Kitty Meeks; Elena Moss

In the authors' words

Inspired by the static problem $(α, β)$ -Dominating Set, we propose a general temporal domination problem, called $(α, β)$ -Temporal Dominating Set ( $(α, β)$ -TDS). We show that this problem encompasses Temporal Dominating Set, and additionally provides first temporal extensions of problems such as $k$ -Dominating Set and $α$ -Dominating Set. In this paper, we study the parameterised complexity of $(α, β)$ -TDS with respect to temporal neighbourhood diversity (TND), temporal modular-width (TMW), and temporal cliquewidth (TCW). We obtain fixed parameter tractability results for all values of $α$ and $β$ with respect to TND; W[1]-hardness with respect to TMW and TCW whenever $β$ is in the problem input, or whenever $α \in (0, 1)$ and $β$ is a fixed constant; and para-NP-hardness with respect to TCW when $α = 0$ and $β = 1$ , or $α = 1$ and $β = 0$ .

Main resultThe abstract does not state a limitation.

The parameterised complexity of generalised temporal domination on temporal graphs with modular structure

In the authors' words

More on Algorithms & complexity that day

4-Block Integer Programming is in FPT

Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties

An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance

Analysis of trade-offs in urban heat mitigation using a Bayesian Optimization framework for an urban canopy layer model

Factorisability of Low Dimensional Non-Negative Integer Matrices