[Rule] X3C to MinimumWeightAndOrGraph

[isPANN]

Source: EXACT COVER BY 3-SETS (ExactCoverBy3Sets)
Target: MINIMUM WEIGHT AND/OR GRAPH SOLUTION (MinimumWeightAndOrGraph)

Motivation: Establishes NP-completeness of finding minimum-weight solution subgraphs in AND/OR DAGs, even when all arc weights are 1 (unit weights). AND/OR graphs are fundamental in AI search (AO* algorithm), game tree evaluation, and hierarchical planning. The reduction from X3C shows that selecting which OR-branches to explore -- the core decision in AO* -- is computationally hard in general DAGs. The result by Sahni (1974) motivated the development of heuristic search algorithms for AND/OR graphs, since exact solutions are intractable.
Reference: Garey & Johnson, Computers and Intractability, A12 MS16; Sahni 1974

GJ Source Entry

[MS16] MINIMUM WEIGHT AND/OR GRAPH SOLUTION
INSTANCE: Directed acyclic graph G = (V, A) with a single source s, a labeling function f(v) ∈ {and, or} for each non-leaf vertex v, a weight function w: A → Z⁺, positive integer K.
QUESTION: Is there a "solution subgraph" G' = (V', A') with s ∈ V' satisfying: for each and-vertex v ∈ V', all arcs from v are in A'; for each or-vertex v ∈ V', at least one arc from v is in A'; and the total weight ∑_{a∈A'} w(a) ≤ K?

Reference: [Sahni, 1974]. Transformation from EXACT COVER BY 3-SETS.
Comment: NP-complete even if all weights are 1. Solvable in polynomial time for rooted trees.

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 MinimumWeightAndOrGraph instance (DAG G, gate types, unit weights, bound K) as follows:

1. Source vertex: Create source vertex s, labeled AND.

2. Element vertices: For each element u ∈ U, create an element vertex v_u as a child of s. Since s is AND, all element vertices must be in any solution. Add arc (s, v_u) with weight 1.

3. Element vertices are OR gates: Label each v_u as OR. The children of v_u correspond to the sets containing element u.

4. Set-element connector vertices: For each set S_j and each element u ∈ S_j, create a leaf vertex l_{j,u} as a child of v_u. Add arc (v_u, l_{j,u}) with weight 1. Since v_u is OR, the solution must pick at least one child (i.e., at least one set covering u).

5. Coupling constraint via shared structure: To enforce that selecting set S_j for one element means selecting it for all three elements in S_j, introduce a "set vertex" w_j for each S_j, labeled AND. Replace the direct leaf connections: instead, for each u ∈ S_j, make l_{j,u} an AND vertex with children being the other elements of S_j routed through w_j. This ensures that choosing S_j to cover one element forces covering the other two as well.

   More precisely: for each set S_j = {a, b, c}, create an AND vertex w_j. From each element vertex v_a, v_b, v_c, add an OR-child pointing to w_j. The children of w_j are leaf vertices corresponding to "S_j covers a, b, c." All arcs have weight 1.

6. Bound K: Set K = 3q + q = 4q (3q arcs from source to element vertices, plus q arcs for the selected set choices). With unit weights, the minimum solution weight equals the number of arcs in the solution subgraph.

   Note: The exact bound depends on the gadget details. With the coupling structure, K encodes that exactly q sets are selected (each covering 3 elements).

Correctness:

• (=>) If C' is an exact cover of size q, the solution subgraph includes: all arcs from s to element vertices (AND, forced), and for each v_u, the arc to the set in C' that covers u. The coupling structure ensures consistency. Total weight = 3q + (additional arcs from coupling) = K.
• (<=) If a solution subgraph of weight <= K exists, the OR choices at element vertices (which set covers each element) must be consistent (due to coupling) and cover all elements, yielding an exact cover of size <= q.

Size Overhead

Symbols:

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

Target metric (code name)	Polynomial (using symbols above)
num_vertices	O(q + m)
num_arcs	O(q + m)

Derivation:

• 1 source + 3q element vertices + O(m) set/coupling vertices + O(m) leaf vertices.
• Arcs: 3q (source to elements) + 3m (elements to set connectors) + O(m) (coupling arcs).
• All weights are 1. Bound K = O(q).
• Exact constants depend on the coupling gadget design.

Validation Method

• Closed-loop test: reduce an ExactCoverBy3Sets instance to MinimumWeightAndOrGraph, solve target with BruteForce (enumerate OR-vertex choices), extract the selected sets, verify they form 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 solution with minimum weight = K.
• Test with a NO X3C instance: U = {1,2,3,4,5,6}, C = {{1,2,3}, {1,4,5}, {2,5,6}}, q = 2. No exact cover; solution weight should exceed K.
• Verify the constructed graph is a valid DAG with a single source and correct AND/OR labels.
• Verify all arc weights are 1 (unit weight case).

Example

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

Exact cover: {S_1} (or {S_2}) covers all elements.

Constructed target instance (MinimumWeightAndOrGraph):
Simplified construction with unit weights:

Vertices:

• s (source, AND gate)
• v_1, v_2, v_3 (element vertices, OR gates)
• l_1, l_2 (leaf vertices representing sets S_1 and S_2)

Arcs (all weight 1):

• (s, v_1), (s, v_2), (s, v_3) -- source to elements (AND: all required)
• (v_1, l_1), (v_2, l_1), (v_3, l_1) -- elements to S_1 representative
• (v_1, l_2), (v_2, l_2), (v_3, l_2) -- elements to S_2 representative

Note: This simplified version doesn't enforce consistency (an OR at v_1 could pick S_1 while v_2 picks S_2). The full reduction uses coupling gadgets to prevent this.

With the full coupling, the optimal solution picks one set (say S_1) for all three elements:

• Include arcs: (s, v_1), (s, v_2), (s, v_3), (v_1, l_1), (v_2, l_1), (v_3, l_1).
• Total weight = 6.
• K = 6 (3 AND-forced arcs + 3 OR-chosen arcs for one set covering all elements).

Answer: YES with K = 6.

References

• [Sahni, 1974]: S. Sahni (1974). "Computationally Related Problems." SIAM Journal on Computing, 3(4), pp. 262-279.
• [Nilsson, 1980]: N.J. Nilsson (1980). Principles of Artificial Intelligence. Tioga Publishing. (AND/OR graphs and AO* algorithm.)
• [Martelli and Montanari, 1973]: A. Martelli, U. Montanari (1973). "Additive AND/OR Graphs." Proceedings of the 3rd International Joint Conference on Artificial Intelligence, pp. 1-11.