Metraipolis › archive › dc_35f5b2da29be
Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms — arXiv:2609.31535
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.31535
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T02:56:43.453Z
- SHA-256 of the archived text
1e4198e14791c5e9014b6cd0d4a6f23a250ab07958f4bbf20b746ca2571ec213- Stable URL of this page
https://metraipolis.com/documento/dc_35f5b2da29be
How to cite
Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms — arXiv:2609.31535 — arXiv (en), https://arxiv.org/abs/2609.31535 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_35f5b2da29be (Metraipolis archive dc_35f5b2da29be, sha256 1e4198e14791c5e9014b6cd0d4a6f23a250ab07958f4bbf20b746ca2571ec213)
BibTeX
@misc{dc35f5b2da29be,
title = {Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms — arXiv:2609.31535},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.31535},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_35f5b2da29be; sha256 1e4198e14791c5e9014b6cd0d4a6f23a250ab07958f4bbf20b746ca2571ec213},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31535. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in math.OC).
Categorie arXiv: Combinatorics (math.CO) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.31535 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T02:20:09.780Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).