[Model] NetworkReliability

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] NetworkReliability"
labels: model
assignees: ''

Motivation

NETWORK RELIABILITY (P96) from Garey & Johnson, A2 ND20. An NP-hard (and not known to be in NP) problem of computing the probability that a set of terminal vertices remains connected when edges fail independently with given probabilities. This problem is fundamental to the design and analysis of communication networks, power grids, and distributed systems. It is marked with (*) in GJ, indicating it is not known to be in NP (the reliability probability may require exponential precision to verify).

Associated rules:

• [Rule] STEINER TREE to NETWORK RELIABILITY #256: SteinerTreeInGraphs -> NetworkReliability (GJ ND20, Rosenthal 1974)

Definition

Name: NetworkReliability
Canonical name: Network Reliability (also: K-Terminal Reliability, All-Terminal Reliability)
Reference: Garey & Johnson, Computers and Intractability, A2 ND20

Mathematical definition:

INSTANCE: Graph G = (V, E), subset V' ⊆ V, a rational "failure probability" p(e), 0 ≤ p(e) ≤ 1, for each e ∈ E, a positive rational number q ≤ 1.
QUESTION: Assuming edge failures are independent of one another, is the probability q or greater that each pair of vertices in V' is joined by at least one path containing no failed edge?

Trait mapping: This is a SatisfactionProblem with Metric = bool. Given a binary edge-survival configuration x ∈ {0, 1}^|E|, evaluate(x) returns true if all terminals in V' are pairwise connected in the subgraph induced by surviving edges (x_e = 1), and false otherwise.

Solver note: The standard BruteForce::find_satisfying() finds one connected edge pattern, NOT the reliability probability. Computing the actual reliability R(G, V', p) requires enumerating all 2^|E| patterns and summing weighted probabilities of connected ones — this is a #P-hard computation beyond the standard solver interface. A custom reliability computation method is needed.

Variables

• Count: |E| binary variables (one per edge), let m = |E|
• Per-variable domain: binary {0, 1} — whether edge e survives (1) or fails (0)
• Meaning: variable x_e = 1 if edge e is operational, x_e = 0 if edge e has failed. A configuration is feasible (evaluate → true) if all terminals in V' are pairwise connected in the subgraph of surviving edges.

Dims

[2; num_edges] — one binary variable per edge.

Schema (data type)

Type name: NetworkReliability
Variants: none (no type parameters)

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E)
terminals	Vec<usize>	The set of terminal vertices V' ⊆ V
failure_probs	Vec<f64>	Failure probability p(e) for each edge e ∈ E
threshold	f64	Reliability threshold q

Notes:

• This problem is NOT known to be in NP. The answer involves computing a probability that may not have a polynomial-size certificate.
• The problem is NP-hard (and the underlying counting problem is #P-complete).
• No type parameters: failure_probs and threshold are fixed f64 fields (problem data, not variant-polymorphic). variant() returns empty.

Size fields

Getter	Meaning
num_vertices()	Number of vertices
num_edges()	Number of edges
num_terminals()	Number of terminal vertices
threshold()	Reliability threshold q

Complexity

• Decision complexity: NP-hard, not known to be in NP. Marked with (*) in GJ.
• Counting complexity: The underlying problem of computing the reliability polynomial is #P-complete (Valiant, 1979). Remains NP-hard even for |V'| = 2 (two-terminal reliability).
• Best known exact algorithm: Exact computation requires enumerating connected subgraphs or using inclusion-exclusion over min-cuts. Time complexity is exponential: O(2^|E| · |V|) in the worst case for general graphs. Binary Decision Diagram (BDD) methods can compute exact reliability for moderately sized graphs. For graphs with bounded treewidth w, exact computation is possible in O(2^w · n) time.
• Complexity string: "2^num_edges * num_vertices"
• Special cases: Polynomial-time solvable for series-parallel graphs, graphs of bounded treewidth, and some other restricted graph classes.
• References:
  • A. Rosenthal (1974). "Computing Reliability of Complex Systems." Ph.D. thesis, University of California, Berkeley.
  • L.G. Valiant (1979). "The Complexity of Enumeration and Reliability Problems." SIAM Journal on Computing, 8(3):410-421.
  • M.O. Ball (1986). "Computational Complexity of Network Reliability Analysis: An Overview." IEEE Transactions on Reliability, R-35(3):230-239.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), subset V' ⊆ V, a rational "failure probability" p(e), 0 ≤ p(e) ≤ 1, for each e ∈ E, a positive rational number q ≤ 1.
QUESTION: Assuming edge failures are independent of one another, is the probability q or greater that each pair of vertices in V' is joined by at least one path containing no failed edge?

Reference: [Rosenthal, 1974]. Transformation from STEINER TREE IN GRAPHS.
Comment: Not known to be in NP. Remains NP-hard even if |V'| = 2 [Valiant, 1977b]. The related problem in which we want two disjoint paths between each pair of vertices in V' is NP-hard even if V' = V [Ball, 1977b]. If G is directed and we ask for a directed path between each ordered pair of vertices in V', the one-path problem is NP-hard for both |V'| = 2 [Valiant, 1977b] and V' = V [Ball, 1977a]. Many of the underlying subgraph enumeration problems are #P-complete (see [Valiant, 1977b]).

How to solve

• It can be solved by (existing) bruteforce. Enumerate all 2^|E| edge survival/failure patterns, for each pattern check if terminals V' are pairwise connected (BFS/DFS), sum the probabilities of connected patterns, compare to threshold q.
• It can be solved by reducing to integer programming. (Not directly — this is a probability computation problem, not a standard optimization problem.)
• Other: BDD-based exact methods for moderate-size graphs; Monte Carlo simulation for estimation; inclusion-exclusion over min-cuts; factoring/decomposition methods for series-parallel graphs.

Example Instance

Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 8 edges:

• Edges: {0,1}, {0,2}, {1,3}, {2,3}, {1,4}, {3,4}, {3,5}, {4,5}
• Terminals V' = {0, 5}
• Failure probabilities: all p(e) = 0.1 (each edge fails with 10% probability, survives with 90%)
• Threshold q = 0.95

Analysis (two-terminal reliability from vertex 0 to vertex 5):

• There are multiple paths from 0 to 5:
  • Path 1: 0→1→3→5 (edges {0,1}, {1,3}, {3,5})
  • Path 2: 0→2→3→5 (edges {0,2}, {2,3}, {3,5})
  • Path 3: 0→1→4→5 (edges {0,1}, {1,4}, {4,5})
  • Path 4: 0→2→3→4→5 (edges {0,2}, {2,3}, {3,4}, {4,5})
• Total search space: 2^8 = 256 edge survival/failure patterns.
• Brute-force enumeration over all 256 patterns yields:
  • 91 connected configurations (terminals 0 and 5 are pairwise reachable)
  • 165 disconnected configurations (terminals not connected)
• Exact reliability = 0.9684 (sum of probabilities of all 91 connected patterns)

Expected Outcome

• Reliability = 0.9684 > q = 0.95 → Answer: YES (the network reliability exceeds the threshold)
• The example has 165 infeasible (disconnected) configurations out of 256 total, demonstrating a non-trivial instance where edge failures can disconnect the terminals.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but poor fit with codebase trait system
Non-trivial	✅ Pass	Distinct feasibility/objective from all existing problems
Correctness	✅ Pass	All three references verified; complexity claims accurate
Well-written	❌ Fail	Fundamental trait-system mismatch; missing/inconsistent sections

Overall: 1 passed, 1 warning, 1 failed (Correctness passed with note)

---

Usefulness

Result: Warning

The problem does not currently exist in the codebase (pred show NetworkReliability returns not found). Network reliability is a well-studied and important problem in combinatorial optimization and network design.

However, there is a fundamental concern about how this problem fits the project's architecture. The codebase's Problem trait requires:

• evaluate(&self, config: &[usize]) -> Metric — evaluates a single configuration
• Metric is either SolutionSize<W> (optimization) or bool (satisfaction)

Network Reliability is fundamentally a probability computation (a counting/#P problem). The reliability value is a weighted sum over all 2^|E| configurations, not a property of any single configuration. While the decision version ("is reliability >= q?") could theoretically be modeled as a satisfaction problem, evaluate() on a single edge-state vector can only check whether terminals are connected in that specific subgraph — it cannot determine the reliability probability. The brute-force "solver" would need to sum probabilities across all configurations rather than searching for a satisfying/optimal one, which is fundamentally different from how BruteForce::find_satisfying() works.

The associated rule (R41: Steiner Tree -> Network Reliability) is also problematic since Steiner Tree is not yet implemented in the codebase, so this problem would be an orphan node in the reduction graph.

The issue should clarify exactly how evaluate() would work and whether the existing solver infrastructure can handle this problem type.

Non-trivial

Result: Pass

NetworkReliability is genuinely distinct from all 24 existing problems in the codebase. No existing problem involves probability computation over exponentially many failure/survival configurations weighted by per-element probabilities. The feasibility constraints (terminal connectivity under random edge failures) and objective (probability threshold) are structurally different from all existing graph, formula, set, algebraic, and miscellaneous problems.

Correctness

Result: Pass

All three cited references are verified:

1. Rosenthal (1974) — "Computing Reliability of Complex Systems," Ph.D. thesis, UC Berkeley. Confirmed to exist via Google Books and academic citations. This is indeed the original reference for the NP-hardness of network reliability, consistent with the Garey & Johnson citation.

2. Valiant (1979) — "The Complexity of Enumeration and Reliability Problems," SIAM Journal on Computing, 8(3):410-421. Verified at https://epubs.siam.org/doi/10.1137/0208032. This paper introduces #P-completeness and proves that the counting version of network reliability is #P-complete. The issue correctly states this.

3. Ball (1986) — "Computational Complexity of Network Reliability Analysis: An Overview," IEEE Transactions on Reliability, R-35(3):230-239. Verified at IEEE Xplore (DOI: 10.1109/TR.1986.4335422). The paper confirms that k-terminal, 2-terminal, and all-terminal reliability problems are all NP-hard.

The complexity claims in the issue are accurate:

• Decision problem is NP-hard and not known to be in NP (marked with (*) in GJ) — correct
• Counting version is #P-complete (Valiant 1979) — correct
• Remains NP-hard for |V'| = 2 — correct (Valiant 1979)
• Best known exact: O(2^|E|) general, O(2^w * n) for treewidth w — reasonable claims

Note: The issue body says "Rosenthal, 1974" but Garey & Johnson actually reference "Rosenthal, 1974" for the transformation, while the issue's Extra Remark section says "[Valiant, 1977b]" for the |V'|=2 result. The 1977b reference is Valiant's earlier technical report; the 1979 paper is the published journal version. This is consistent.

Well-written

Result: Fail

Several issues found:

4a. Fundamental Trait-System Mismatch:
The issue does not address how NetworkReliability maps to the Problem trait. Specifically:

• What does evaluate(&self, config: &[usize]) -> Metric return? The issue says Metric = bool (satisfaction), but evaluating a single configuration only tells you if terminals are connected in that configuration, not whether the reliability exceeds threshold q. The answer to the decision question requires summing over all configurations.
• The brute-force solver section says "Enumerate all 2^|E| edge failure patterns, for each pattern check if terminals V' are connected, sum the probabilities of connected patterns." This is correct algorithmically, but it does not fit BruteForce::find_satisfying() which searches for a single satisfying configuration — it would need a fundamentally different solver.
• The issue should either (a) explain how to adapt the trait system, or (b) propose a different Metric type, or (c) acknowledge that this problem requires special handling.

4b. Missing Complexity String:
The Complexity section does not provide a specific declare_variants! complexity string in the required format (e.g., "2^num_edges"). It lists several algorithmic approaches but no single concrete bound suitable for the macro.

4c. Symbol Inconsistencies:

• The Schema section defines failure_probs: Vec<f64> but does not explain how floating-point probabilities interact with the codebase's integer-oriented weight system (WeightElement trait, NumericSize supertrait).
• threshold: f64 is a field but there is no corresponding getter method listed (should be threshold() or similar).
• The "Size Overhead" table (required for the issue template) is missing entirely.

4d. Example Quality:

• The example is adequate in structure (6 vertices, 8 edges, specific probabilities) but the analysis uses hand-wavy approximations ("approximately 0.1^2 = 0.01", "Reliability ~ 0.99") rather than computing the exact reliability value. For a problem whose entire point is exact probability computation, the example should show the exact answer (or at least a precise enough calculation for verification).
• The brute-force approach (256 configurations) is small enough to enumerate completely — the example should do so.

4e. Naming Convention:
Per CLAUDE.md naming rules, this problem is not an optimization problem (no Maximum/Minimum prefix needed), so NetworkReliability is acceptable.

Recommendations

• Clarify trait mapping: The most natural fit may be to treat each configuration as a binary edge vector and have evaluate() return bool (are terminals connected?), then implement a custom probability-computation method outside the standard solver. Alternatively, consider whether this problem truly fits the Problem trait or needs trait extensions.
• Provide exact example solution: Compute the exact reliability for the 6-vertex, 8-edge example (256 states is tractable by hand or script).
• Add complexity string: Something like "2^num_edges" for the general case.
• Add Size Overhead table: Even if no reductions are planned yet, the template requires this section.
• Consider the Steiner Tree dependency: The associated rule (R41) requires Steiner Tree to be implemented first. Note this dependency explicitly.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; concrete reduction from SteinerTreeInGraphs (exists in codebase)
Non-trivial	✅ Pass	Genuinely distinct probability computation problem
Correctness	✅ Pass	All references verified; example answer (YES) confirmed (exact reliability = 0.9684)
Well-written	❌ Fail	Trait-system mismatch unaddressed; missing required sections; example uses inaccurate approximations

Overall: 3 passed, 0 warnings, 1 failed

---

Usefulness

Result: Pass

NetworkReliability does not exist in the codebase (86 types currently). The issue mentions "STEINER TREE IN GRAPHS → NETWORK RELIABILITY" as an associated rule — SteinerTreeInGraphs is already implemented, providing a concrete connection to the reduction graph. Motivation is substantive: fundamental to communication network design, power grids, and distributed systems.

Non-trivial

Result: Pass

No existing problem involves probability computation over weighted edge-failure configurations. The feasibility constraint (terminal pairwise connectivity under random edge failures) combined with the probability-threshold objective is structurally distinct from all 86 existing problem types. This is genuinely a counting/#P-type problem, not a re-skin of any existing graph/satisfaction/optimization problem.

Correctness

Result: Pass

Reference verification:

1. Rosenthal (1974) — Ph.D. thesis, UC Berkeley. Standard reference for NP-hardness of network reliability, cited by Garey & Johnson. ✅
2. Valiant (1979) — "The Complexity of Enumeration and Reliability Problems," SIAM J. Computing 8(3):410–421. Proves #P-completeness of the counting version and NP-hardness for |V'|=2. ✅
3. Ball (1986) — "Computational Complexity of Network Reliability Analysis: An Overview," IEEE Trans. Reliability R-35(3):230–239. Survey confirming k-terminal, 2-terminal, and all-terminal reliability are NP-hard. ✅

All complexity claims are accurate: NP-hard and not known to be in NP, #P-complete counting version, remains NP-hard for |V'|=2.

Example verification (brute-force, 256 configurations):

• Exact two-terminal reliability (0→5): 0.968425 (91 connected, 165 disconnected configs)
• Threshold q = 0.95 → 0.968425 > 0.95 → YES ✅
• Note: the issue claims "Reliability ~ 0.99" which is inaccurate (actual: 0.9684). The final YES answer is correct, but the intermediate approximation is misleading.

Well-written

Result: Fail

4a. Fundamental trait-system mismatch (critical):
The issue does not explain how NetworkReliability maps to the Problem trait. The codebase's evaluate(&self, config: &[usize]) -> Metric evaluates a single configuration. For Metric = bool, evaluate() can check whether terminals are connected in one edge-survival pattern. However:

• BruteForce::find_satisfying() finds one satisfying configuration — this does not answer whether reliability ≥ q
• BruteForce::find_all_satisfying() finds all connected patterns, but doesn't compute weighted probability sums
• The decision question requires summing ∏p_e over all connected subgraphs, which is fundamentally different from finding satisfying/optimal configurations

The issue must clarify: (a) what evaluate() returns, (b) how the solver infrastructure handles probability computation, and (c) whether trait extensions are needed.

4b. Missing required sections:

• Dims: Not explicitly stated. Should be [2; num_edges] (binary per edge).
• Size fields: Mentioned in schema notes (num_vertices, num_edges, num_terminals) but no dedicated section with getter names and meanings.
• Complexity string: No concrete declare_variants! string provided. Needs something like "2^num_edges" for general case.

4c. Example quality:

• Example size is appropriate (2^8 = 256, in [128, 10000] range) ✅
• Example has adequate infeasible configs (165 out of 256) ✅
• Not fully worked: Uses hand-wavy approximations ("approximately 0.1^2 = 0.01", "Reliability ~ 0.99") instead of the exact value (0.9684). For a probability computation problem, the example should show the exact answer. The ~0.99 estimate is ~2% off from the true value.
• The inclusion-exclusion sketch is illustrative but incomplete — four paths are listed but the actual calculation using inclusion-exclusion on dependent paths is not carried out.

4d. Symbol consistency:

• threshold field in Schema has no corresponding getter method listed in Size fields
• failure_probs: Vec<f64> raises questions about interaction with the WeightElement trait system (which is integer-oriented)

Recommendations

1. Address the trait-system fit — the most critical fix. Options: (a) define evaluate() as terminal connectivity check, then implement a custom reliability() method that sums over all configs; (b) propose a new CountingProblem trait extension; (c) reframe as a satisfaction problem where the "configuration" encodes the full enumeration result somehow.
2. Add explicit Dims section: [2; num_edges]
3. Add explicit Size fields section with getter names: num_vertices(), num_edges(), num_terminals(), threshold()
4. Provide concrete complexity string: "2^num_edges" for the general brute-force bound
5. Compute exact reliability in the example: 0.968425 (verified by enumeration of all 256 patterns)
6. Note the SteinerTreeInGraphs dependency for the associated rule explicitly

[isPANN]

Fix-issue changelog

• Added Trait mapping section: SatisfactionProblem with evaluate(x) = terminals connected. Added solver note explaining #P-hard probability computation vs standard find_satisfying().
• Added Dims section: [2; num_edges]
• Added Size fields table: num_vertices(), num_edges(), num_terminals(), threshold()
• Added Complexity string: "2^num_edges * num_vertices"
• Corrected complexity bound from O(2^|E|) to O(2^|E| · |V|)
• Replaced hand-wavy example approximation ("~0.99") with exact reliability = 0.9684 (brute-force over 256 patterns: 91 connected, 165 disconnected)
• Added Expected Outcome section with exact answer
• Updated Schema to "no type parameters" (f64 fields are problem data, not variant-polymorphic)
• Updated associated rule reference to [Rule] STEINER TREE to NETWORK RELIABILITY #256
• Standardized math notation (⊆, ∈, ≤)

Applied by /fix-issue.