Temporal graphs model systems whose interactions change over time. In such networks, temporal reachability domination seeks a small seed set whose influence can reach all vertices. However, one successful temporal path is often not enough in practical settings, where repeated exposure or backup delivery may be needed. To address this, this paper introduces the \(q\)-Temporal Reachability Dominating Set (\(q\)-TaRDiS), which requires every vertex to be reachable from at least \(q\) distinct seeds, together with a budgeted version that maximizes threshold coverage under a fixed seed limit. The study presents the model, establishes basic properties, shows membership in NP, and notes NP-hardness in the unrestricted case. It also shows that the problem reduces to set multicover once temporal reachability sets are computed, leading to an exact integer programming model and an efficient greedy solution strategy. Experiments on synthetic temporal networks show that the greedy method is near-optimal on small instances and that threshold-based seed sets provide better robustness under random temporal edge deletion. These results show that threshold temporal domination offers a practical and analyzable framework for resilient diffusion in dynamic networks.
Temporal graphs model systems whose interactions change over time. In such networks, temporal reachability domination seeks a small seed set whose influence can reach all vertices. However, one successful temporal path is often not enough in practical settings, where repeated exposure or backup delivery may be needed. To address this, this paper introduces the \(q\)-Temporal Reachability Dominating Set (\(q\)-TaRDiS), which requires every vertex to be reachable from at least \(q\) distinct seeds, together with a budgeted version that maximizes threshold coverage under a fixed seed limit. The study presents the model, establishes basic properties, shows membership in NP, and notes NP-hardness in the unrestricted case. It also shows that the problem reduces to set multicover once temporal reachability sets are computed, leading to an exact integer programming model and an efficient greedy solution strategy. Experiments on synthetic temporal networks show that the greedy method is near-optimal on small instances and that threshold-based seed sets provide better robustness under random temporal edge deletion. These results show that threshold temporal domination offers a practical and analyzable framework for resilient diffusion in dynamic networks.
