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

Abstract

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 \emph{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.