{"id":"arxiv/2609.31535","url":"https://arxiv.org/abs/2609.31535","tags":["math.CO","math.OC"],"score":0,"title":"Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms","domain":"math.CO","source":"arxiv","authors":["Julian D. Allagan","Kevin Pereyra","William A. Massey"],"reviews":0,"subject":"math.CO","summary":"On a network with a fixed set of verified sources, discounted averaging induces an equilibrium support $h_i^S=\\mathbb{E}_i[λ^{T_S}]$, the discounted probability that a random walk reaches $S$ before attenuation. We define the \\emph{discounted hitting domination number} $δ_{λ,τ}(G)$ as the minimum number of sources required to guarantee $h_i^S\\geτ$ 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{}}