<p><a href="https://arxiv.org/abs/1806.00917" rel="nofollow noreferrer">This paper</a> shows an exact mapping from reliability to exact model counting. From that point on, exact counters (like miniC2D) can be used to compute reliability. Not sure if useful runtime bounds exist for this scheme.</p>

CC BY-SA 4.0
2024-01-09T13:29:01.073Z
2024-01-09T13:29:01.073Z
delete000
<p>In the network reliability problem, we are given an undirected graph <span class="math-container">$G$</span> on <span class="math-container">$n$</span> vertices and a parameter <span class="math-container">$p\in (0,1)$</span>, and are tasked with determining the probability that <span class="math-container">$G$</span> becomes disconnected (i.e., some two nodes in the graph are not connected by a path) if we independently and randomly delete each edge of <span class="math-container">$G$</span> with probability <span class="math-container">$p$</span>.</p>
<p>It is known that this problem is <span class="math-container">$\text{#P}$</span>-hard, so it is unlikely to admit a polynomial-time algorithm.</p>
<p><strong>Question:</strong> What is the fastest known (exact, not approximate) algorithm for solving network reliability?</p>

<ds.algorithms><graph-theory><graph-algorithms><counting-complexity><exp-time-algorithms>
What is the fastest algorithm for computing exact network reliability?
Naysh
# What is the fastest algorithm for computing exact network reliability?

(Asked by: username_0 on 2024-01-08)

In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i.e., some two nodes in the graph are not connected by a path) if we independently and randomly delete each edge of $G$ with probability $p$.

It is known that this problem is $\text{#P}$-hard, so it is unlikely to admit a polynomial-time algorithm.

**Question:** What is the fastest known (exact, not approximate) algorithm for solving network reliability?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, counting-complexity, exp-time-algorithms


---

## 1 answers

### Answer by username_1 on 2024-01-09. Score: 2

[This paper](https://arxiv.org/abs/1806.00917) shows an exact mapping from reliability to exact model counting. From that point on, exact counters (like miniC2D) can be used to compute reliability. Not sure if useful runtime bounds exist for this scheme.


---

