Approximating Two-Terminal Network Reliability
Statement
Does two-terminal reliability, the probability that still reaches 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.
Record
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
proof attempt · #1
Weiming Feng, Yucheng Fu and Heng Guo, using GPT-5.6 Sol UltraThat credit came with the record as it was imported. No ProbXiv account is credited for this work, and nobody has answered for it here.
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.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.