Algorithms for Domination Problems on Temporal Graphs

Abstract

Temporal graphs are graphs whose edge set can change on a discrete set of tau ordered time steps. We research temporal domination problems. We consider several static domination problems which describe how a vertex can be dominated, and several temporal domination requirements which describe when and how often a vertex should be dominated. By combining static domination problems with temporal domination requirements, we obtain temporal domination problems.

For the Temporary Domination requirement, each vertex needs to be dominated in at least one time step, while the Permanent Domination requirement requires them to be dominated in all time steps. k-Fold Domination generalizes this: each vertex should be dominated on at least k time steps. Periodic Domination requires each vertex to be dominated at least once every theta time steps for some period theta. Evolving Domination instead asks for a separate domination function for each time step. Marching Domination requires each vertex to be dominated in every time step, but allows us to change the domination function in between time steps, simulating the movements of armies protecting points of interest (vertices).

Each of these temporal domination requirements can be combined with static domination problems. We apply these six temporal domination requirements to three static domination problems: Dominating Set, Roman Domination and Weak Roman Domination to define 18 temporal domination problems. We provide exact exponential and parameterized algorithms that solve all of these problems, except for the permanent, periodic and k-fold variants of Weak Roman Domination.

Furthermore, we also give definitions for the family of static domination problems Defense-Like Domination and their natural temporal counterpart: Temporal Defense-Like Domination.