Kevin Pereyra

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 \emph{discounted hitting domination number} $\delta_{\lambda,\tau}(G)$ as the minimum nu...