[Rule] X3C to MinimumFaultDetectionTestSet

[isPANN]

Source: EXACT COVER BY 3-SETS (ExactCoverBy3Sets)
Target: FAULT DETECTION IN DIRECTED GRAPHS (FaultDetectionDirectedGraphs)

Motivation: Establishes NP-completeness of finding minimum-size test sets for fault detection in combinational circuits modeled as DAGs. The reduction from X3C shows that selecting a small set of input-output test pairs that covers all possible single faults is as hard as exact cover. This is a foundational result in VLSI testing and hardware verification, demonstrating that optimal test generation is intractable even for simple DAG structures. The result holds even when there is only a single output node.
Reference: Garey & Johnson, Computers and Intractability, A12 MS18; Ibaraki, Kameda, Toida 1977

GJ Source Entry

[MS18] FAULT DETECTION IN DIRECTED GRAPHS
INSTANCE: Directed acyclic graph G = (V, A) with inputs I (in-degree 0) and outputs O (out-degree 0), positive integer K.
QUESTION: Is there a test set T ⊆ I × O with |T| ≤ K such that, for each arc a ∈ A, some (i, o) ∈ T has a on a path from i to o?

Reference: [Ibaraki, Kameda, and Toida, 1977]. Transformation from EXACT COVER BY 3-SETS.
Comment: NP-complete even for |O| = 1. Polynomial if K ≥ |I| · |O|.

Reduction Algorithm

Summary:
Given an X3C instance (universe U = {1, 2, ..., 3q}, collection C = {S_1, ..., S_m} of 3-element subsets of U), construct a FaultDetectionDirectedGraphs instance (DAG G = (V, A), threshold K) as follows:

1. Input vertices: Create one input vertex i_j for each set S_j in C. So |I| = m.

2. Element vertices: Create one intermediate vertex e_u for each element u in U. So there are 3q element vertices.

3. Output vertex: Create a single output vertex o. (The reduction achieves |O| = 1.)

4. Arc construction:

   • For each set S_j = {a, b, c}, add arcs (i_j, e_a), (i_j, e_b), (i_j, e_c). These represent that test input i_j "reaches" elements a, b, c.
   • For each element vertex e_u, add arc (e_u, o). This ensures every element arc connects to the output.

5. Target arcs to cover: The arcs (e_u, o) for u = 1, ..., 3q are the "fault sites." A test pair (i_j, o) covers arc (e_u, o) if and only if u is in S_j (there is a path i_j -> e_u -> o).

6. Threshold K = q. We need q input vertices (test pairs) whose corresponding sets cover all 3q elements.

Correctness:

• (=>) If C' is a sub-collection of q sets forming an exact cover, then T = {(i_j, o) : S_j in C'} has |T| = q = K and covers all arcs (e_u, o) since every element u is in exactly one S_j in C'.
• (<=) If T is a test set of size <= q covering all arcs (e_u, o), each test (i_j, o) covers arcs for elements in S_j. Since all 3q element-to-output arcs must be covered by q tests each covering 3, we need exactly q tests covering disjoint triples -- an exact cover.

Note: The arcs (i_j, e_u) are also in the DAG but are automatically covered whenever (i_j, o) is in T (since i_j -> e_u -> o is the path). The critical arcs are the 3q arcs (e_u, o).

Size Overhead

Symbols:

• q = |U|/3 (universe size / 3)
• m = |C| = num_sets (number of 3-element subsets)
• u = |U| = 3q = universe_size

Target metric (code name)	Polynomial (using symbols above)
num_vertices	m + 3q + 1
num_arcs	3m + 3q
num_inputs	m
num_outputs	1

Derivation:

• Vertices: m input vertices + 3q element vertices + 1 output vertex.
• Arcs: 3 arcs per set (input to elements) = 3m, plus 3q arcs (elements to output).
• Threshold K = q.

Validation Method

• Closed-loop test: reduce an ExactCoverBy3Sets instance to FaultDetectionDirectedGraphs, solve target with BruteForce (enumerate subsets of I x O of size <= K), extract the selected inputs, verify they correspond to an exact cover.
• Test with a YES X3C instance: U = {1,2,3,4,5,6}, C = {{1,2,3}, {4,5,6}}, q = 2. Should find test set of size 2.
• Test with a NO X3C instance: U = {1,2,3}, C = {{1,2,3}, {1,2,3}} (duplicate), q = 1. Should find test set of size 1 (trivially yes since one set covers all). Better NO instance: U = {1,2,3,4,5,6}, C = {{1,2,3}, {1,4,5}, {2,5,6}}, q = 2. No exact cover exists; verify test set of size 2 is insufficient.
• Verify the constructed graph is a valid DAG and all arcs are reachable from inputs.

Example

Source instance (ExactCoverBy3Sets):
Universe U = {1, 2, 3, 4, 5, 6} (q = 2).
Collection C = {S_1 = {1, 2, 3}, S_2 = {4, 5, 6}, S_3 = {1, 4, 5}}.

Exact cover: {S_1, S_2} covers all elements with 2 disjoint sets.

Constructed target instance (FaultDetectionDirectedGraphs):
Vertices: inputs {i_1, i_2, i_3}, elements {e_1, ..., e_6}, output {o}. Total: 10 vertices.

Arcs:

• (i_1, e_1), (i_1, e_2), (i_1, e_3) -- from S_1
• (i_2, e_4), (i_2, e_5), (i_2, e_6) -- from S_2
• (i_3, e_1), (i_3, e_4), (i_3, e_5) -- from S_3
• (e_1, o), (e_2, o), (e_3, o), (e_4, o), (e_5, o), (e_6, o) -- elements to output

Threshold K = 2.

Verification:
Test set T = {(i_1, o), (i_2, o)}:

• (i_1, o) covers arcs: (e_1, o), (e_2, o), (e_3, o) via paths i_1 -> e_u -> o.
• (i_2, o) covers arcs: (e_4, o), (e_5, o), (e_6, o) via paths i_2 -> e_u -> o.
• All 6 element-to-output arcs covered. Also (i_1, e_1), etc. are covered. |T| = 2 <= K. Answer: YES.

Test set T = {(i_1, o), (i_3, o)}: covers {e_1, e_2, e_3} union {e_1, e_4, e_5} = {e_1, e_2, e_3, e_4, e_5}. Missing: (e_6, o). Answer: NO for this test set.

References

• [Ibaraki, Kameda, and Toida, 1977]: T. Ibaraki, T. Kameda, S. Toida (1977). "On Minimal Test Sets for Combinational Logic Circuits." IEEE Transactions on Computers, C-26(10), pp. 959-965.