[Model] MinimumFaultDetectionTestSet

[isPANN]

Motivation

FAULT DETECTION IN DIRECTED GRAPHS (MS18) from Garey & Johnson, A12. Given a directed acyclic graph (DAG) with designated input vertices (in-degree 0) and output vertices (out-degree 0), find a minimum-size set of input-output paths that covers every vertex in the graph. This models VLSI test generation: each path represents a test that activates a signal from an input to an output, and every component (vertex) must be exercised by at least one test. NP-hard even when there is only one output (Ibaraki, Kameda, Toida). Applications in hardware testing, fault diagnosis, and network monitoring.

Definition

Name: MinimumFaultDetectionTestSet
Reference: Garey & Johnson, Computers and Intractability, A12 MS18

Mathematical definition:

INSTANCE: A directed acyclic graph G = (V, A) with inputs I = {v ∈ V : in-degree(v) = 0} and outputs O = {v ∈ V : out-degree(v) = 0}.
OBJECTIVE: Find a test set T ⊆ I × O of minimum cardinality such that for every vertex v ∈ V, there exists a test (i, o) ∈ T where v lies on some path from i to o in G.

Equivalently: every vertex must be covered by at least one input-to-output path in the selected test set. The objective value is Min(|T|).

Variables

• Count: |I| × |O| (one per input-output pair)
• Per-variable domain: {0, 1}
• Meaning: Whether each input-output pair (i, o) is included in the test set T. The coverage of pair (i, o) is the set of all vertices that lie on some path from i to o. The constraint is that every vertex in V must be covered by at least one selected pair.

Schema

Type name: MinimumFaultDetectionTestSet
Variants: none

Field	Type	Description
num_vertices	usize	Number of vertices
arcs	Vec<(usize, usize)>	Directed arcs A, each (u, v) where u is parent, v is child
inputs	Vec<usize>	Input vertices I (in-degree 0)
outputs	Vec<usize>	Output vertices O (out-degree 0)

Complexity

• NP-hardness: NP-hard even for |O| = 1 (Ibaraki, Kameda, Toida; G&J cites reduction from X3C).
• Best known exact algorithm: O*(2^(num_inputs * num_outputs)) by brute-force over test-pair subsets. The problem is a special case of SET COVER (vertices are elements, each (i,o) pair covers vertices on paths from i to o).
• Complexity string: "2^(num_inputs * num_outputs)"
• Polynomial special cases: Series-parallel DAGs.

Extra Remark

Full book text:

INSTANCE: Directed acyclic graph G = (V, A), with I = {v ∈ V : in-degree(v) = 0} and O = {v ∈ V : out-degree(v) = 0}, positive integer K.
QUESTION: Is there a set of K or fewer paths, each starting at a vertex of I and ending at a vertex of O, such that every vertex in V lies on at least one of the paths?

Reference: [Ibaraki, Kameda, and Toida]. Transformation from X3C.
Comment: NP-complete even for |O| = 1.

Note: The original G&J formulation asks for K paths covering all vertices. We reformulate equivalently as selecting input-output pairs (each pair implicitly selects a path), and minimize the number of selected pairs. The coverage of pair (i, o) is the set of vertices reachable from i that can also reach o.

How to solve

• It can be solved by (existing) bruteforce. (Precompute coverage sets for each (i,o) pair via forward/backward reachability; enumerate subsets of pairs; find minimum subset covering all vertices.)
• It can be solved by reducing to integer programming.
• Other:

Reduction Rule Crossref

(Planned: ExactCoverBy3Sets → MinimumFaultDetectionTestSet, following G&J)

Example Instance

Input:
DAG with V = {v0, v1, v2, v3, v4, v5, v6} (7 vertices).
Inputs I = {v0, v1}, Outputs O = {v5, v6}.
Arcs: (v0,v2), (v0,v3), (v1,v3), (v1,v4), (v2,v5), (v3,v5), (v3,v6), (v4,v6).

Coverage of each input-output pair:

• (v0, v5): vertices on paths v0→v2→v5 and v0→v3→v5 → covers {v0, v2, v3, v5}
• (v0, v6): vertices on path v0→v3→v6 → covers {v0, v3, v6}
• (v1, v5): vertices on path v1→v3→v5 → covers {v1, v3, v5}
• (v1, v6): vertices on paths v1→v3→v6 and v1→v4→v6 → covers {v1, v3, v4, v6}

Optimal test set T = {(v0, v5), (v1, v6)}, size 2:

• (v0, v5) covers {v0, v2, v3, v5}
• (v1, v6) covers {v1, v3, v4, v6}
• Union = {v0, v1, v2, v3, v4, v5, v6} = V ✓

Why size 1 is impossible: No single pair covers all 7 vertices. The best single pair (v0, v5) covers only 4 vertices, missing v1, v4, v6.

Suboptimal test set: T = {(v0, v5), (v0, v6), (v1, v6)}, size 3 — covers all vertices but uses an unnecessary extra pair.

Expected Outcome

Optimal value: Min(2) — the minimum test set size is 2, achieved uniquely by T = {(v0, v5), (v1, v6)}. Out of 15 possible subsets of 4 pairs, there are 4 feasible test sets with 3 distinct sizes (2, 3, 4).

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	No planned reduction to/from an existing problem is mentioned
Non-trivial	✅ Pass	Distinct feasibility constraints (path-coverage in DAGs) from all existing problems
Correctness	❌ Fail	Problem definition contradicts G&J MS18; reference year incorrect
Well-written	❌ Fail	Missing expected outcome section; naming concerns; definition errors propagate

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The problem FaultDetectionDirectedGraphs does not exist in the codebase yet. However, the issue body does not mention any concrete planned reduction rule connecting this problem to the existing reduction graph. An orphan node without any planned reduction has limited value. At minimum, the issue should mention a planned reduction to or from an existing problem (e.g., a reduction from Exact Cover by 3-Sets, or a reduction to ILP/SetCovering).

Verdict: Warn — novel problem, but no planned reductions stated.

Non-trivial

The problem involves finding minimum-size path covers in DAGs with designated source/sink vertices, which is structurally distinct from all existing problems in the codebase. No existing problem captures this exact feasibility constraint.

Verdict: Pass.

Correctness

3a: Definition — CRITICAL ERROR.

The G&J MS18 problem ("Fault Detection in Directed Graphs") asks whether there exist K or fewer paths from input vertices to output vertices such that every vertex in V lies on at least one path. The issue instead defines the problem as finding test pairs (i, o) such that every arc is covered by at least one path from i to o. These are fundamentally different problems:

• G&J MS18 (vertex coverage): Find K paths from inputs to outputs covering all vertices.
• Issue definition (arc coverage): Find K input-output pairs covering all arcs.

The arc-coverage formulation is essentially a set-cover variant over arcs, while the vertex-coverage formulation is a path-cover problem. The issue's definition does not match the cited reference.

3b: Reference year error.

The issue cites "Ibaraki, Kameda, Toida 1977" but the actual published paper is:

T. Ibaraki, T. Kameda, S. Toida, "On Minimal Test Sets for Locating Single Link Failures in Networks," IEEE Transactions on Computers, vol. 30, no. 3, pp. 182–190, 1981.

No 1977 publication by these authors on this topic could be verified. The 1981 paper also addresses a somewhat different problem (locating/distinguishing single link failures, not just detecting them), so even the relevance of this citation needs re-examination.

3c: Complexity claim.

The complexity string "2^(num_inputs * num_outputs)" is described as "brute-force over test pairs." This is not the best known algorithm — it is simply exhaustive enumeration. The issue itself notes that the problem is a special case of Set Cover, which has better exact algorithms (e.g., O*(2^n) where n is the universe size = number of arcs, not |I|×|O|). Furthermore, for the correct vertex-coverage formulation, the complexity analysis would be entirely different. No literature-backed complexity bound is provided.

Verdict: Fail.

Well-written

4a: Information completeness issues:

• Expected Outcome: The example provides a "YES" answer with K=2 and shows a valid test set, but there is no explicit "Expected Outcome" section with the optimal objective value and justification as required by the template. The optimization version (minimize |T|) should state the minimum value and why it is optimal.
• How to solve: Only brute-force is checked. The issue notes the problem is a special case of Set Cover, suggesting an ILP formulation is natural, but does not check the ILP box or link a companion rule issue.

4b: Definition completeness:

The definition conflates two different problems. The "INSTANCE" section describes one formulation (arc coverage via test pairs), while G&J MS18 describes another (vertex coverage via paths). This makes the definition unimplementable as stated, because it is unclear which problem is actually intended.

4c: Naming convention:

The name FaultDetectionDirectedGraphs does not follow the project's optimization naming convention. If this is a minimization problem (minimize |T|), it should use the Minimum prefix (e.g., MinimumFaultDetectionTestSet). If it is a decision/feasibility problem, the current name may be acceptable, but the issue should clarify.

4d: Example quality:

The example is reasonable in structure (5 vertices, 4 arcs, 2 inputs, 2 outputs) and shows a worked solution. However, because the definition itself is wrong (arc coverage vs vertex coverage), the example illustrates the wrong problem. Additionally, the example is small enough that it may not exercise the problem's structure sufficiently — all paths go through the single bottleneck vertex 2, so the coverage is nearly trivial.

Verdict: Fail.

Recommendations

1. Fix the definition to match G&J MS18: the problem should ask for K or fewer paths from input vertices to output vertices such that every vertex is covered, not every arc.
2. Update the reference year for Ibaraki, Kameda, Toida from 1977 to 1981, and verify the paper actually proves NP-completeness of the vertex-coverage formulation (or find the correct reference).
3. Add a planned reduction (e.g., from ExactCoverBy3Sets, as suggested by G&J) to connect this problem to the reduction graph.
4. Research better complexity bounds — the vertex path-cover problem in DAGs is related to minimum path cover, which is solvable in polynomial time via maximum matching on bipartite graphs (Dilworth's theorem / König's theorem). If G&J MS18 is indeed polynomial-time solvable in the standard formulation, it may not belong in this NP-hard reduction library at all. This needs careful investigation — the NP-completeness may come from additional constraints not captured in the issue.
5. Add an Expected Outcome section with the optimal value and justification.
6. Clarify the problem type (decision vs. optimization) and adjust the name accordingly.

[isPANN]

Renamed from FaultDetectionDirectedGraphs to MinimumFaultDetectionTestSet. Converted from decision (bound K) to optimization framing: find a minimum-size test set covering all arcs. Removed threshold field from schema. Created companion rule issue for X3C reduction.

[isPANN]

Fix-issue changelog

• Critical fix: changed coverage constraint from arcs to vertices per G&J MS18. The original issue defined arc coverage (every arc on a path), but G&J MS18 asks for vertex coverage (every vertex on at least one input-output path).
• Reference: removed incorrect year 1977 for Ibaraki, Kameda, Toida
• Example: new 7-vertex DAG (2 inputs, 2 outputs, 8 arcs). 4 feasible test sets with 3 distinct sizes (2, 3, 4). Unique optimal T = {(v0,v5), (v1,v6)} of size 2, verified by brute-force enumeration.
• Expected Outcome: added section with Min(2) and feasibility statistics
• Crossref: added planned ExactCoverBy3Sets → MinimumFaultDetectionTestSet reduction

Applied by /fix-issue.