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 hiS=𝔼i[λTS], 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 hiS≥τ 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 λr+1<τ≤(λ/Δ)r, then δλ,τ(G) equals the distance-r domination number. This yields NP-completeness and APX-completeness at (λ,τ)=(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 (λ,τ), 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.
Related
- Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
- On k-limited domination: complexity and Cartesian products
- On k-limited domination: complexity and Sierpiński graphs
- The parameterised complexity of generalised temporal domination on temporal graphs with modular structure
- Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity
BibTeX
@misc{allagan2026discounted,
title = {{Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms}},
author = {Julian D. Allagan and Kevin Pereyra and William A. Massey},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31535},
eprint = {2609.31535},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31535},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms
AU - Julian D. Allagan
AU - Kevin Pereyra
AU - William A. Massey
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31535
UR - https://arxiv.org/abs/2609.31535
AB - On a network with a fixed set of verified sources, discounted averaging induces an equilibrium support h_i^S=𝔼_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≥τ 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 λ^r+1<τ≤(λ/Δ)^r, then δ_λ,τ(G) equals the distance-r domination number. This yields NP-completeness and APX-completeness at (λ,τ)=(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 (λ,τ), 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.
ER -