Parameter complexity analysis of temporal domination problems in modular graphs
The parameterised complexity of generalised temporal domination on temporal graphs with modular structure
Discrete Mathematics
Summary
This work looks at a problem where you want to pick nodes in a changing network so that they can influence or cover their neighbors over time in specific ways. The authors study how hard it is to solve this problem depending on how the network is structured and which parameters you choose. They find situations where the problem can be solved efficiently and others where it becomes very difficult. This helps us understand when certain network analysis tasks are feasible as things change over time.
What this means in practice
- •For network analysts: Determine when influence spreading or monitoring tasks on time-varying networks are computationally feasible based on network modular structures and selected parameters.
- •For algorithm designers: Guide algorithm development by identifying specific structural conditions under which temporal domination problems become tractable or intractable.
A theory result. No direct application yet.
Authors
Jessica Enright, Kitty Meeks, Elena Moss
Abstract
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$.