Approximating Two-Terminal Network Reliability

Precise statement

Does two-terminal reliability, the probability that $s$ still reaches $t$ when edges fail independently, admit a fully polynomial-time randomised approximation scheme? Asked explicitly in Kannan's 1994 survey and left open while the all-terminal cases were settled by Karger and by Guo and Jerrum. Answered positively for general graphs, both directed and undirected. The complementary unreliability question is shown to be BIS-hard, so it is unlikely to admit one.

The source statement is reproduced for indexing with attribution. Mathematical correctness requires domain-expert or mechanical review. VibeMath has not independently audited statement fidelity, correctness, priority, or novelty.

What AI did

GPT-5.6 Sol Ultra

The abstract credits GPT-5.6 Sol Ultra with the key idea of the algorithm. The three authors develop the analysis, the BIS-hardness result and the write-up.

Provider: OpenAI · Prompt public: unknown · Independence: unknown

Verification boundary

unreviewed

arXiv preprint; not yet peer-reviewed.

Correctness: unknown · statement fidelity: unaudited · peer review: none

Timeline

1. 2026-08-03

   arXiv:2608.02523 - Approximating two-terminal network reliability

   VibeMathed reports this item as resolved. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.

Known method families

argument (source-reported)

Source-reported tools: argument.

Independent: unknown · difference confidence: 0

What remains uncertain

VibeMath has not independently audited the mathematical statement, proof, or novelty claim.

• VibeMath has not independently verified the mathematical claim.
• AI-attempt independence and training-data exposure are unknown unless explicitly documented.
• VibeMath has not independently audited the mathematical statement, proof, or novelty claim.