[Model] NetworkSurvivability

[isPANN]

---

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

Motivation

NETWORK SURVIVABILITY (P97) from Garey & Johnson, A2 ND21. A classical problem in network reliability analysis that asks whether the probability that all edges fail (i.e., at least one endpoint or the edge itself fails for every edge) meets a given threshold. It is used as a target in the reduction from VERTEX COVER (R42). Notably, this problem is not known to be in NP since computing the exact failure probability may require exponential-precision arithmetic.

Associated rules:

• R42: VERTEX COVER -> NETWORK SURVIVABILITY (incoming)

Definition

Name: NetworkSurvivability

Canonical name: NETWORK SURVIVABILITY
Reference: Garey & Johnson, Computers and Intractability, A2 ND21

Mathematical definition:

INSTANCE: Graph G = (V,E), a rational "failure probability" p(x), 0 ≤ p(x) ≤ 1, for each x ∈ V∪E, a positive rational number q ≤ 1.
QUESTION: Assuming all edge and vertex failures are independent of one another, is the probability q or greater that for all {u,v} ∈ E at least one of u, v, or {u,v} will fail?

Variables

• Count: |V| + |E| binary variables (one per element of V∪E), each representing whether that vertex or edge has failed.
• Per-variable domain: {0, 1} where 1 = "element has failed" and 0 = "element is operational."
• Meaning: A configuration assigns a failure/operational status to each vertex and edge. The question asks whether the probability (over independent Bernoulli failures with parameters p(x)) that every edge {u,v} has at least one of u, v, or {u,v} in the "failed" state meets or exceeds the threshold q.

Schema (data type)

Type name: NetworkSurvivability
Variants: graph topology (graph type parameter G)

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V,E)
vertex_failure_prob	Vec<f64>	Failure probability p(v) for each vertex v ∈ V
edge_failure_prob	Vec<f64>	Failure probability p(e) for each edge e ∈ E
threshold	f64	The probability threshold q

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The problem asks whether the compound event "every edge has at least one failed endpoint or is itself failed" has probability ≥ q.
• Not known to be in NP: verifying a YES answer requires summing over exponentially many failure configurations.

Complexity

• Best known exact algorithm: Exact computation of network reliability is #P-complete (Valiant, 1979). Brute-force enumeration over all 2^(|V|+|E|) failure configurations takes O(2^(|V|+|E|) * |E|) time. For graphs with bounded treewidth w, linear-time FPT algorithms exist with complexity O(2^(O(w)) * (|V|+|E|)).
• NP-hardness: The problem is NP-hard (Rosenthal, 1974; proved by reduction from VERTEX COVER). It is not known to be in NP since computing the probability exactly may require summing over exponentially many configurations.
• References:
  • A. Rosenthal (1974). "Computing Reliability of Complex Systems." University of California.
  • L.G. Valiant (1979). "The Complexity of Enumeration and Reliability Problems." SIAM Journal on Computing, 8(3):410–421.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), a rational "failure probability" p(x), 0 ≤ p(x) ≤ 1, for each x ∈ V∪E, a positive rational number q ≤ 1.
QUESTION: Assuming all edge and vertex failures are independent of one another, is the probability q or greater that for all {u,v} ∈ E at least one of u, v, or {u,v} will fail?

Reference: [Rosenthal, 1974]. Transformation from VERTEX COVER.
Comment: Not known to be in NP.

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming.
• Other: Enumerate all 2^(|V|+|E|) failure configurations, compute the probability of each configuration (product of independent Bernoulli probabilities), sum over configurations where every edge has at least one failed endpoint or is itself failed, and compare with q. This is exact but exponential.

Example Instance

Instance 1 (YES — probability meets threshold):
Graph G with 4 vertices {0, 1, 2, 3} and 4 edges:

• Edges: e0={0,1}, e1={1,2}, e2={2,3}, e3={0,3} (cycle C_4)
• Vertex failure probabilities: p(0) = 0.5, p(1) = 0.5, p(2) = 0.5, p(3) = 0.5
• Edge failure probabilities: p(e0) = 0.5, p(e1) = 0.5, p(e2) = 0.5, p(e3) = 0.5
• Threshold: q = 0.01
• Each element fails independently with probability 0.5. The event "all edges covered by a failure" requires that for each of the 4 edges, at least one of its endpoints or the edge itself fails. With 8 independent coin flips at p=0.5, the probability that all 4 edges are "covered" is relatively high (since each edge has 3 chances to be covered, each with p=0.5, giving 1 - 0.5^3 = 0.875 per edge, and these events overlap significantly).
• Answer: YES (the probability exceeds 0.01)

Instance 2 (NO — probability below threshold):
Graph G with 6 vertices {0,1,2,3,4,5} and 7 edges:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,0}, {0,3}
• All failure probabilities: p(x) = 0.01 for all x ∈ V∪E
• Threshold: q = 0.5
• With very low failure probabilities, it is extremely unlikely that every edge has a failure among its endpoints or itself. The probability is far below 0.5.
• Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Problem is novel, but only one incoming reduction planned and no outgoing reductions; problem is not known to be in NP
Non-trivial	✅ Pass	Genuinely distinct problem — probabilistic failure threshold over graph elements
Correctness	⚠️ Warn	References exist but some claims are imprecise or conflated
Well-written	❌ Fail	Missing template sections, examples lack computed values, symbol inconsistencies

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem does not exist in the codebase (pred show NetworkSurvivability returns unknown). This is a novel addition. However, there are concerns:

• Only one planned reduction (Vertex Cover -> NetworkSurvivability, incoming). No outgoing reductions are listed. This makes the problem a leaf node in the reduction graph with limited utility for demonstrating reduction chains.
• Not known to be in NP: The issue itself acknowledges this. The codebase primarily handles NP-hard optimization and satisfaction problems where solutions can be verified in polynomial time. A problem where even verification requires exponential-precision arithmetic is architecturally unusual — the SatisfactionProblem trait expects Metric = bool evaluation to be feasible for any given configuration, but here evaluating the truth of the answer requires summing over all configurations, not checking a single one.
• Motivation is adequate but could be stronger — it explains the GJ classification and the incoming reduction, but doesn't articulate why this problem is useful beyond being in the GJ catalog.

Non-trivial

Pass. NetworkSurvivability has a genuinely different structure from all 24 existing problems. It involves:

• Per-element (vertex and edge) failure probabilities
• A probability threshold over independent Bernoulli random variables
• The compound event that every edge is "covered" by at least one failure

This is not isomorphic to or a variant of any existing problem (MinimumVertexCover, MaxCut, etc.).

Correctness

The references exist but some claims need correction:

1. Valiant (1979) — Confirmed. "The Complexity of Enumeration and Reliability Problems," SIAM Journal on Computing, 8(3):410-421. This paper establishes #P-completeness of network reliability computation, not NP-hardness per se. The issue conflates #P-completeness (counting) with NP-hardness (decision).

2. Rosenthal (1974) — Confirmed. "Computing Reliability of Complex Systems," Ph.D. thesis, University of California, Berkeley. The Garey & Johnson book cites this as the source of the NP-hardness proof via reduction from Vertex Cover.

3. GJ numbering: The issue says "P97" but GJ uses letter-number codes (e.g., ND21). The "P97" designation is unclear — it may refer to a page number or an unofficial numbering. The "A2 ND21" designation appears correct for the Network Design section of the GJ appendix.

4. Complexity claim issue: The issue states brute-force is O(2^(|V|+|E|) * |E|) which is reasonable but not precisely justified. The claim about "bounded treewidth" FPT algorithms is plausible but no specific reference is cited for it.

Well-written

Fail. Several issues:

4a: Information Completeness

• Variables section has the AI-unverified warning but the content is reasonable.
• How to solve only checks "Other" — neither brute-force nor ILP are checked. The "Other" description is essentially brute-force enumeration, so the brute-force box should be checked instead. This creates confusion about solver integration.

4b: Definition Completeness

• The problem is defined as a decision/satisfaction problem (Metric = bool), but the evaluate() function would need to compute a probability over all 2^(|V|+|E|) configurations just to evaluate a single "configuration." This is a fundamental mismatch with the Problem trait: evaluate() is called per-configuration, but the answer depends on all configurations. The issue does not address how dims(), evaluate(), or the variable semantics would work with the Problem trait.

4c: Symbol and Notation Consistency

• The schema uses vertex_failure_prob and edge_failure_prob as field names, but the issue doesn't specify getter methods or size fields that would be used in overhead expressions (e.g., num_vertices, num_edges).
• The symbol p(x) is used for failure probability in the definition but the schema uses separate Vec<f64> fields — this is fine but should be explicitly connected.

4d: Example Quality

• Instance 1: The answer "YES (the probability exceeds 0.01)" is hand-waved. No actual probability computation is shown. The rough estimate "1 - 0.5^3 = 0.875 per edge" is stated but the actual joint probability is not computed. For a worked example, the exact probability should be calculated.
• Instance 2: Similarly hand-waved with "far below 0.5" — no actual computation.
• Neither example is "fully worked" in the sense that a reader could verify the answer by hand.

Recommendations

• Architectural concern: Consider whether this problem fits the Problem trait at all. The evaluate(config) -> bool pattern assumes you can check a single configuration. For NetworkSurvivability, the "answer" is a property of the probability distribution over all configurations, not a property of any single configuration. This may require a different trait or a creative reinterpretation (e.g., treating each configuration as a "scenario" and checking whether at least one endpoint/edge fails for every edge in that scenario, then using brute-force to sum probabilities).
• Compute the example probabilities exactly for the small instances. Instance 1 (4 vertices, 4 edges, 8 elements) has only 2^8 = 256 configurations, which is easy to enumerate.
• Clarify the solver story: If brute-force works by enumerating all 2^(|V|+|E|) configurations, checking coverage, and summing probabilities, then check the brute-force box and explain how it maps to find_satisfying().
• Add at least one outgoing reduction to make this problem a useful node in the reduction graph, not just a dead end.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem with concrete incoming reduction from VertexCover
Non-trivial	✅ Pass	Genuinely distinct — probabilistic failure threshold over graph elements
Correctness	⚠️ Warn	Valiant (1979) confirmed; Rosenthal (1974) uncertain; examples verified correct
Well-written	❌ Fail	Missing Dims and Size fields sections; examples not fully worked; architectural concern unaddressed

Overall: 2 passed, 0 failed, 1 warning, 1 failed

---

Usefulness

Pass. NetworkSurvivability does not exist in the codebase. The issue mentions a concrete incoming reduction from Vertex Cover (which is implemented). The problem is a leaf node (no outgoing reductions planned), but having at least one concrete reduction prevents orphan status. Motivation is adequate — it identifies the GJ classification and the planned reduction.

Note: The problem is "not known to be in NP," which is architecturally unusual for this codebase. However, the SatisfactionProblem trait can still work if evaluate(config) checks whether a single failure pattern covers all edges (per-configuration check), with the probability computation handled externally.

Non-trivial

Pass. NetworkSurvivability has genuinely different structure from all existing problems:

• Per-element (vertex AND edge) independent failure probabilities
• Probability threshold over compound Bernoulli event
• "All edges covered by failure" feasibility condition

Not isomorphic to any existing problem, and cannot be modeled as a graph/weight variant of an existing type.

Correctness

Warn. Mixed verification results:

Reference	Verdict	Details
Valiant (1979), SIAM J. Computing 8(3):410–421	✅ Confirmed	Correct title, author, year, journal, pages. Establishes #P-completeness of network reliability.
Rosenthal (1974), UC thesis	⚠️ Uncertain	Author and institution are plausible, but the exact year may be 1977 rather than 1974. The specific claim of NP-hardness via Vertex Cover reduction is unusual — more standard references include Ball (1980) and Provan & Ball (1983).

Issues found:

• The Complexity section conflates #P-completeness (counting, Valiant) with NP-hardness (decision, Rosenthal). These are related but distinct concepts. The issue should clarify which result applies to the decision version.
• The claim about "bounded treewidth FPT algorithms" cites no reference.
• The brute-force complexity O(2^(|V|+|E|) · |E|) is reasonable.

Example verification (via brute-force enumeration):

• Instance 1 (C4, all p=0.5, q=0.01): Exact probability = 161/256 ≈ 0.6289 ≥ 0.01 → YES ✅ matches claim
• Instance 2 (6 vertices, 7 edges, all p=0.01, q=0.5): Exact probability ≈ 0.0000021 < 0.5 → NO ✅ matches claim
• Both instances have abundant suboptimal feasible solutions (159 and 3791 respectively).

Well-written

Fail. Several required sections are missing or incomplete:

4a: Missing required sections

• Dims: Not present. Should specify [2; |V| + |E|] (binary variables for each vertex and edge).
• Size fields: Not present. Should list getter names and meanings (e.g., num_vertices, num_edges, num_elements).
• Expected Outcome: The examples state YES/NO but do not provide computed probability values. For the satisfaction problem, the expected outcome should include the exact probability and explain why it does/doesn't meet the threshold.

4b: Definition completeness

• The definition faithfully reproduces GJ ND21, which is well-formed.
• However, the issue does not address how evaluate(config) -> bool maps to this problem. The natural interpretation is: evaluate checks whether a single failure pattern covers all edges (returns true if for every edge {u,v}, at least one of u, v, or {u,v} is marked as failed). This makes the problem fit SatisfactionProblem, but the GJ question is about the probability over all configurations, not about finding a single satisfying configuration. The issue must clarify this mapping.

4c: Symbol and notation consistency

• Schema field vertex_failure_prob and edge_failure_prob are not connected to any getter methods or size fields.
• No overhead expressions to cross-check (no outgoing reductions), but size fields are still required for the model.

4d: Example quality

• ❌ Examples are not fully worked. Instance 1 hand-waves "the probability exceeds 0.01" without computing it. Instance 2 says "far below 0.5" without a value. The exact probabilities should be stated (0.6289 and 0.0000021 respectively).
• ✅ Both examples have the right answer (verified by enumeration).
• ✅ Both examples have abundant suboptimal feasible solutions.

4e: How to solve

• The "Other" checkbox is checked with a description that IS brute-force enumeration. The brute-force checkbox should be checked instead, or the distinction between per-configuration evaluation and probability computation should be clarified.

Recommendations

• Add Dims section: [2; num_vertices + num_edges]
• Add Size fields section with getter names (e.g., num_vertices(), num_edges(), num_elements())
• Compute and state exact probabilities in the examples (161/256 ≈ 0.6289 for Instance 1)
• Clarify the evaluate() semantics: per-configuration check (does this failure pattern cover all edges?) vs. the probability question
• Address how find_satisfying() relates to the GJ decision question — the BruteForce solver finds one covering pattern, but the GJ question asks about cumulative probability
• Fix the Rosenthal reference (verify year; consider citing Ball 1980 or Provan & Ball 1983 as alternative/additional references)
• Check the brute-force box instead of "Other" in How to solve, and clarify that probability computation requires enumerating all configurations

[isPANN]

On Hold

Putting this on hold — NetworkSurvivability (ND21) is a (*) problem (not known to be in NP). The underlying computation is #P-complete, which doesn't fit cleanly into the standard SatisfactionProblem trait. Same situation as #235 (NetworkReliability, ND20). May revisit later if we decide to support #P problems systematically.