[Rule] STEINER TREE to NETWORK RELIABILITY

[isPANN]

---

name: Rule
about: Propose a new reduction rule
title: "[Rule] STEINER TREE IN GRAPHS to NETWORK RELIABILITY"
labels: rule
assignees: ''
canonical_source_name: 'STEINER TREE IN GRAPHS'
canonical_target_name: 'NETWORK RELIABILITY'
source_in_codebase: false
target_in_codebase: false

Source: STEINER TREE IN GRAPHS
Target: NETWORK RELIABILITY
Motivation: Establishes NP-hardness of NETWORK RELIABILITY via polynomial-time reduction from STEINER TREE IN GRAPHS. This is a notable reduction because the target problem is not known to be in NP (computing the exact reliability probability may require exponential precision). The reduction, due to Rosenthal (1974), shows that if we could efficiently determine whether the reliability of a network exceeds a threshold, we could solve the Steiner tree problem. This connects combinatorial optimization (Steiner trees) with probabilistic network analysis.

Reference: Garey & Johnson, Computers and Intractability, ND20, p.211

GJ Source Entry

[ND20] NETWORK RELIABILITY (*)
INSTANCE: Graph G=(V,E), subset V' <= V, a rational "failure probability" p(e), 0 <= p(e) <= 1, for each e in 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]).

Reduction Algorithm

Summary:
Given a SteinerTreeInGraphs instance (G = (V, E), w, R, B) where G is an undirected graph with edge weights w(e) in Z0+, terminal set R <= V, and weight bound B, construct a NetworkReliability instance (G', V', p, q) as follows:

1. Graph construction: Use the same graph G' = G = (V, E). The terminal set is V' = R.

2. Failure probability assignment: Assign uniform failure probability p(e) = p for all edges e in E, where p is chosen as a specific rational value in (0, 1) that makes the reduction work. The exact value of p depends on the structure of G and the weight bound B.

   The key idea is: the reliability of the network (probability that all terminals in R are connected) is a polynomial in (1-p), and this polynomial has a specific relationship to the number of connected subgraphs spanning R weighted by their sizes. A Steiner tree of weight <= B exists if and only if the reliability exceeds a carefully chosen threshold q.

3. Threshold construction: Set the reliability threshold q to a value that distinguishes between:

   • Graphs where a Steiner tree of weight <= B exists (higher reliability)
   • Graphs where no such tree exists (lower reliability)

   Specifically, when p is very small (close to 0), the dominant term in the reliability polynomial corresponds to the minimum-weight Steiner tree. If this minimum weight is <= B, the reliability is approximately 1 - O(p^{B+1}), which exceeds the threshold q. If the minimum weight exceeds B, the reliability drops below q.

4. Alternative formulation (Rosenthal's approach): Rosenthal's original reduction works by observing that the K-terminal reliability R(G, V', p) can be expressed as:

   R(G, V', p) = sum over all edge subsets S that connect V' of: prod_{e in S} (1-p(e)) * prod_{e not in S} p(e)

   The Steiner tree problem asks whether there exists a connected subgraph spanning R with at most B edges (in the unit-weight case). By choosing p appropriately, the threshold on R(G, V', p) encodes whether such a subgraph exists.

5. Solution extraction: This reduction is for decision problems only (NP-hardness proof). There is no direct solution extraction; the reduction shows that an oracle for Network Reliability would solve Steiner Tree.

Note: This is an NP-hardness reduction (not NP-completeness), because Network Reliability is not known to be in NP. The problem is actually #P-hard for computing the exact reliability (Valiant, 1979).

Size Overhead

Symbols:

• n = num_vertices of source SteinerTreeInGraphs instance (|V|)
• m = num_edges of source SteinerTreeInGraphs instance (|E|)
• k = num_terminals of source instance (|R|)

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices
num_edges	num_edges
num_terminals	num_terminals

Derivation:

• The graph is unchanged: same vertices, same edges, same terminal set.
• The transformation only introduces the failure probabilities p(e) and threshold q.
• This is a parameter-setting reduction, not a structural transformation.

Validation Method

• Closed-loop test: reduce a SteinerTreeInGraphs instance to NetworkReliability, compute the exact reliability by brute-force enumeration of all 2^|E| edge failure patterns, verify that reliability >= q iff a Steiner tree of weight <= B exists
• Test with a graph where the minimum Steiner tree is known (e.g., a tree graph where R includes all leaves) and verify the reliability threshold is correctly calibrated
• Test with unit-weight graphs for simplicity in verification
• Note: exact reliability computation is exponential, so only small instances (|E| <= 20) are practical for brute-force validation

Example

Source instance (SteinerTreeInGraphs):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 8 edges, all unit weight:

• Edges: {0,1}, {0,2}, {1,3}, {2,3}, {1,4}, {3,4}, {3,5}, {4,5}
• Terminals R = {0, 5}
• Weight bound B = 3

Minimum Steiner tree connecting vertices 0 and 5:

• Path 0-1-4-5: weight 3 (edges {0,1}, {1,4}, {4,5})
• Path 0-2-3-5: weight 3 (edges {0,2}, {2,3}, {3,5})
• Path 0-1-3-5: weight 3 (edges {0,1}, {1,3}, {3,5})
• Minimum Steiner tree weight = 3 = B, so answer is YES.

Constructed target instance (NetworkReliability):

Same graph G with 6 vertices and 8 edges.

• Terminals V' = {0, 5}
• Failure probabilities: p(e) = 0.01 for all edges (chosen small so reduction works)
• Threshold: q = (1 - 0.01)^3 * polynomial correction ~ 0.97 (calibrated so that existence of a weight-3 Steiner tree implies reliability >= q)

Reliability computation (approximate):

• There are multiple paths from 0 to 5: three paths of length 3 (listed above), plus longer paths.
• P(at least one path works) is very high when p = 0.01.
• Minimum edge cut between 0 and 5 has size 2 (e.g., {0,1} and {0,2}).
• P(disconnected) <= C(cut_size, failures) ~ p^2 = 0.0001.
• Reliability ~ 1 - 0.0001 = 0.9999 >> q.
• Answer: YES (reliability exceeds threshold).

If B = 2 (no Steiner tree of weight <= 2 exists since minimum path length is 3):

• The threshold q would be recalibrated higher so that the reliability for minimum tree weight 3 does NOT exceed the new threshold for B=2.
• Answer: NO.

References

• [Rosenthal, 1974]: [Rosenthal1974] A. Rosenthal (1974). "Computing Reliability of Complex Systems". University of California.
• [Valiant, 1977b]: [Valiant1977b] Leslie G. Valiant (1977). "The complexity of enumeration and reliability problems". Computer Science Dept., University of Edinburgh.
• [Ball, 1977b]: [Ball1977b] M. O. Ball (1977). "".
• [Ball, 1977a]: [Ball1977a] M. O. Ball (1977). "Network Reliability and Analysis: Algorithms and Complexity". Cornell University.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Both source and target problems are missing from the codebase
Non-trivial	⚠️ Warn	Reduction described as identity graph + parameter setting; unclear structural transformation
Correctness	❌ Fail	Reduction algorithm is speculative; key details fabricated; reference year errors
Well-written	❌ Fail	Algorithm is a hand-wave, not an implementable procedure; multiple template issues

Overall: 0 passed, 2 failed, 2 warnings

---

Usefulness

Neither SteinerTreeInGraphs nor NetworkReliability exist in the codebase. Running pred show for both returns errors. This means the reduction cannot be implemented until both models are added first. As a novel reduction (no existing path), this would Pass if the problems existed, but the missing prerequisites make it impossible to evaluate overhead comparisons. The motivation is well-written and explains the significance of the reduction clearly.

Verdict: Warn — cannot fully evaluate until both models exist.

Non-trivial

The issue's own description raises a concern: the "Size Overhead" section explicitly states this is a "parameter-setting reduction, not a structural transformation" — the graph is unchanged (num_vertices = num_vertices, num_edges = num_edges, num_terminals = num_terminals), and the reduction only introduces failure probabilities and a threshold. The algorithm section describes choosing p and q values but does not construct any new graph structure.

However, parameter-setting reductions from optimization to decision problems can be non-trivial if the parameter choice requires careful analysis (as it does here — the threshold q must encode the weight bound B through the reliability polynomial). This is a borderline case.

Verdict: Warn — the reduction is not structurally trivial in the traditional sense, but the issue's own overhead table confirms it is an identity mapping on the graph, which may not fit this codebase's reduction framework well.

Correctness

Several serious issues:

1. Fabricated algorithm details. The "Reduction Algorithm" section admits the construction is speculative with phrases like "where p is chosen as a specific rational value... that makes the reduction work" and "the exact value of p depends on the structure of G and the weight bound B." The actual construction of p and q — the core of the reduction — is never specified. Steps 2-4 are hand-waving, not a concrete algorithm. The issue even provides an "Alternative formulation" that is just the definition of reliability, not a reduction.

2. Reference year errors.

   • The issue cites "[Valiant, 1977b]" but Valiant's paper "The Complexity of Enumeration and Reliability Problems" was published in SIAM J. Computing, vol. 8, pp. 410-421, 1979, not 1977. The Garey & Johnson reference "[Valiant, 1977b]" likely refers to a 1977 technical report, but the issue's References section gives the wrong year context.
   • "[Ball, 1977b]" has an empty title field — literally "" — which is clearly incomplete.

3. Rosenthal reference is real but incomplete. Rosenthal (1974) is a real UC Berkeley thesis, later published as "Computing the Reliability of Complex Networks" in SIAM J. Appl. Math. 32, pp. 384-393 (1977). The reduction from Steiner Tree to Network Reliability is attributed to Rosenthal in Garey & Johnson (ND20). However, the issue does not reproduce Rosenthal's actual construction — it speculates about what it might look like.

4. The example is fabricated. The example uses "p = 0.01" and "q ~ 0.97" with no justification. The "polynomial correction" is undefined. The verification that "reliability ~ 0.9999 >> q" is a rough approximation, not a worked example of the actual reduction. The "If B = 2" case is hand-waved entirely.

5. Fundamental problem type mismatch. Steiner Tree is an optimization problem (minimize total weight), but Network Reliability as stated in GJ is a decision/threshold problem (is reliability >= q?). The reduction goes from an optimization problem's decision version to another decision problem. This is fine for NP-hardness proofs but awkward for this codebase, which implements reductions between problem instances with solution extraction. The issue acknowledges "There is no direct solution extraction" — which means this reduction fundamentally does not fit the ReduceTo<T> trait pattern.

Verdict: Fail — the reduction algorithm is not the actual Rosenthal construction but a speculative reconstruction. Key parameters (p, q) are undefined. References have errors.

Well-written

Multiple issues:

1. Algorithm is not implementable. The reduction algorithm is a high-level sketch, not a step-by-step procedure. The core parameters p and q are described conceptually but never given concrete formulas. A programmer could not implement this.

2. Missing/incomplete references. [Ball, 1977b] has an empty title. The BibTeX key format is inconsistent.

3. Example is not fully worked. The example uses approximate values ("~ 0.97", "~ 0.9999") instead of exact computations. The threshold q is not actually computed — it is described as "calibrated so that..." without specifying how.

4. Symbol inconsistency. The algorithm uses w for weights and B for the weight bound, but the overhead table uses code metric names (num_vertices, num_edges, num_terminals) without defining the relationship. The source problem is described as (G, w, R, B) in the algorithm but (G = (V, E), w, R, B) format is inconsistent with the example which uses {0, 1, 2, 3, 4, 5}.

5. No solution extraction. The issue explicitly states "There is no direct solution extraction" — this is a fundamental gap for this codebase's reduction framework, which requires extract_solution() to map target solutions back to source solutions.

6. All sections marked with AI-generated warnings. Every substantive section carries the <!-- Unverified: AI-generated --> disclaimer, indicating the content has not been verified by the issue author.

Verdict: Fail — the algorithm is not implementable, the example is approximate, and the reduction lacks solution extraction.

Recommendations

• The actual Rosenthal (1974/1977) construction should be consulted directly. The current algorithm section is speculative and does not reproduce the real reduction.
• Network Reliability is a decision problem not known to be in NP, which makes it unusual for this codebase. Consider whether this reduction fits the project's framework (which expects ReduceTo<T> with solution extraction).
• Both source and target models would need to be implemented first. Consider filing [Model] issues for SteinerTreeInGraphs and NetworkReliability before this rule issue.
• Fix the Valiant reference year (1979, not 1977) and provide the actual title for Ball (1977b).
• The example should use exact arithmetic with the actual threshold formula from Rosenthal's construction, not approximate values.