Metraipolis › archive › dc_034bbfe5477b

A Fully Polynomial Randomized Approximation Scheme for Hypergraph Unreliability — arXiv:2610.41714

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.41714
License (as archived): CC0-1.0
Archived: 2026-11-02T05:06:47.344Z
SHA-256 of the archived text: 1430149b2b6dc55f1823f56d25f64a214b31580ed0f973d161c9f388b7961581
Stable URL of this page: https://metraipolis.com/documento/dc_034bbfe5477b

How to cite

A Fully Polynomial Randomized Approximation Scheme for Hypergraph Unreliability — arXiv:2610.41714 — arXiv (en), https://arxiv.org/abs/2610.41714 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_034bbfe5477b (Metraipolis archive dc_034bbfe5477b, sha256 1430149b2b6dc55f1823f56d25f64a214b31580ed0f973d161c9f388b7961581)

BibTeX

@misc{dc034bbfe5477b,
  title = {A Fully Polynomial Randomized Approximation Scheme for Hypergraph Unreliability — arXiv:2610.41714},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41714},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_034bbfe5477b; sha256 1430149b2b6dc55f1823f56d25f64a214b31580ed0f973d161c9f388b7961581},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41714. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We give a fully polynomial randomized approximation scheme for all-terminal unreliability in explicitly represented undirected hypergraphs of arbitrary rank. The algorithm estimates the probability that independent hyperedge failures disconnect the hypergraph, allowing a different rational failure probability for every edge. For a common failure probability, this improves the quasi-polynomial approximation schemes of Cen, Li, and Panigrahi to polynomial time and answers the polynomial-time approximation question reiterated in their subsequent work on graphs. The construction turns their representative-survival bound into an importance sampler whose relative second moment is bounded solely in terms of the number of vertices. We protect one randomly chosen representative pair during contraction, correct the path likelihood, and divide by the number of pairs surviving at the end. The resulting unbiased estimator has relative second moment at most $\binom n2$, even when unreliability is exponentially small. A minimum-cut normalization makes this estimator implementable with polynomially bounded precision: the residual likelihood becomes a survival probability in an auxiliary absorbing process, which admits rational discretization with a fixed random-bit budget. Logarithmic rate rounding and an exact weighted minimum cut extend the construction to unequal rational failure probabilities. The algorithm's worst-case running time and random-bit usage are polynomial in the input length, the inverse relative error, and $\log(1/\delta)$ for confidence $1-\delta$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.41714 — 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-11-02T04:50:28.139Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).