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[λ^{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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.31535
curl -X POST /api/v1/records/arxiv/2609.31535/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.31535/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'