Hypergraph Unreliability in Quasi-Polynomial Time
<|reference_start|>Hypergraph Unreliability in Quasi-Polynomial Time: The hypergraph unreliability problem asks for the probability that a hypergraph gets disconnected when every hyperedge fails independently with a given probability. For graphs, the unreliability problem has been studied over many decades, and multiple fully polynomial-time approximation schemes are known starting with the work of Karger (STOC 1995). In contrast, prior to this work, no non-trivial result was known for hypergraphs (of arbitrary rank).   In this paper, we give quasi-polynomial time approximation schemes for the hypergraph unreliability problem. For any fixed $\varepsilon \in (0, 1)$, we first give a $(1+\varepsilon)$-approximation algorithm that runs in $m^{O(\log n)}$ time on an $m$-hyperedge, $n$-vertex hypergraph. Then, we improve the running time to $m\cdot n^{O(\log^2 n)}$ with an additional exponentially small additive term in the approximation.<|reference_end|>
@article{cen2024hypergraph,
    title={Hypergraph Unreliability in Quasi-Polynomial Time},
    author={Ruoxu Cen, Jason Li, Debmalya Panigrahi},
    journal={arXiv preprint arXiv:2403.18781},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.18781},
    primaryClass={cs.DS}
}