Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms

On a network with a fixed set of verified sources, discounted averaging induces an equilibrium support $h_i^S={\mathbb{E}}_i[{\lambda }^{T_S}]$, the discounted probability that a random walk reaches $S$ before attenuation. We define the discounted hitting domination number ${\delta }_{\lambda ,\tau }(G)$ as the minimum number of sources required to guarantee $h_i^S\ge \tau$ at every vertex. Although this potential is known through penalized and group hitting probabilities, the associated minimum-cardinality uniform-coverage problem appears to be new. Aggregate support is monotone submodular, while the uniform-floor problem is an exact submodular-cover problem. Moreover, if ${\lambda }^{r+1}<\tau \le {\left(\frac{\lambda }{\Delta }\right)}^r$, then ${\delta }_{\lambda ,\tau }(G)$ equals the distance-$r$ domination number. This yields NP-completeness and APX-completeness at $(\lambda ,\tau )=(1/4,1/14)$ on graphs of maximum degree three. For spiders, we obtain an exact finite-state characterization and a polynomial-time algorithm for every fixed rational pair $(\lambda ,\tau )$, and show that the branching vertex need not belong to a minimum source set. Finally, an exact mixed-integer linear formulation certifies optimal placements on a real network and a synthetic graph and demonstrates substantial differences from degree, closeness, and classical domination.