[Model] MinimumWeightAndOrGraph

[isPANN]

Motivation

MINIMUM WEIGHT AND/OR GRAPH SOLUTION (MS16) from Garey & Johnson, A12. Given a DAG with a single source, where each non-leaf vertex is labeled AND or OR, and arcs have positive integer weights, find a minimum-weight solution subgraph rooted at the source. An AND vertex requires all its children in the solution; an OR vertex requires at least one child. This models AI game tree search (AND/OR trees), the AO* algorithm, and hierarchical planning. NP-hard even with unit weights (Sahni 1974). Polynomial for rooted trees via dynamic programming.

Definition

Name: MinimumWeightAndOrGraph
Reference: Garey & Johnson, Computers and Intractability, A12 MS16; Sahni 1974

Mathematical definition:

INSTANCE: A directed acyclic graph G = (V, A) with a single source s (a vertex with in-degree 0 from which all other vertices are reachable), a function f: V \ Leaves → {AND, OR} labeling each non-leaf vertex, and a weight function w: A → Z⁺ assigning positive integer weights to arcs.
OBJECTIVE: Find a solution subgraph G' = (V', A') of G of minimum total arc weight such that:

1. s ∈ V';
2. For every AND vertex v ∈ V', all children of v (and the corresponding arcs) are in G';
3. For every OR vertex v ∈ V', at least one child of v (and the corresponding arc) is in G';
4. Every non-leaf vertex in V' satisfies its AND/OR constraint.

The objective value is Min(Σ_{a ∈ A'} w(a)).

Variables

• Count: m = |A| (one per arc)
• Per-variable domain: {0, 1}
• Meaning: Whether each arc is included in the solution subgraph. The source must be solved (its AND/OR constraint satisfied), propagating recursively to all included non-leaf vertices.

Schema

Type name: MinimumWeightAndOrGraph
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
source	usize	The single source vertex s
gate_types	Vec<Option<bool>>	Gate type for each vertex: Some(true) = AND, Some(false) = OR, None = leaf
arc_weights	Vec<i32>	Positive integer weight for each arc (parallel to arcs vector)

Complexity

• NP-hardness: NP-hard even with unit weights (Sahni 1974). The NP-completeness proof reduces from 3-SATISFIABILITY (see npcomplete.owu.edu).
• Best known exact algorithm: O*(2^num_arcs) by brute-force. A smarter approach enumerates choices for each OR vertex: O*(∏ out-degree of OR vertices).
• Complexity string: "2^num_arcs"
• Polynomial special cases: Rooted trees (O(|V|) via bottom-up DP). OR-only graphs reduce to shortest path.

Extra Remark

Full book text:

INSTANCE: Directed acyclic graph G = (V, A) with a designated source vertex s having in-degree 0, a labeling function f: V \ Leaves → {AND, OR}, a weight function w: A → Z⁺, positive integer K.
QUESTION: Is there a solution subgraph G' = (V', A') with s ∈ V' satisfying AND/OR constraints and Σ_{a ∈ A'} w(a) ≤ K?

Reference: [Sahni, 1974].
Comment: NP-complete even with unit weights.

Note: The original G&J formulation is a decision problem with bound K. We use the equivalent optimization formulation: minimize total arc weight.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate choices for each OR vertex; AND constraints are then deterministic. Evaluate total weight; return minimum.)
• It can be solved by reducing to integer programming.
• Other:

Reduction Rule Crossref

• [Rule] X3C to MinimumWeightAndOrGraph #929 — [Rule] X3C to MinimumWeightAndOrGraph (note: Sahni 1974 actually reduces from 3SAT; this rule may need source correction)

Example Instance

Input:
DAG with V = {v0, v1, v2, v3, v4, v5, v6} (7 vertices), source s = v0.

Gate types:

• v0: AND (source — must include both children)
• v1: OR (choose one child)
• v2: OR (choose one child)
• v3, v4, v5, v6: LEAF

Arcs with weights:

• (v0, v1): w=1, (v0, v2): w=2
• (v1, v3): w=3, (v1, v4): w=1
• (v2, v5): w=4, (v2, v6): w=2

Since v0 is AND, both arcs (v0,v1) and (v0,v2) are always included (cost 1+2=3). The choices are:

• OR at v1: pick v3 (cost +3) or v4 (cost +1)
• OR at v2: pick v5 (cost +4) or v6 (cost +2)

All 4 feasible solutions:

1. v1→v4, v2→v6: total = 1+2+1+2 = 6 (optimal)
2. v1→v3, v2→v6: total = 1+2+3+2 = 8
3. v1→v4, v2→v5: total = 1+2+1+4 = 8
4. v1→v3, v2→v5: total = 1+2+3+4 = 10

Optimal solution: arcs {(v0,v1), (v0,v2), (v1,v4), (v2,v6)}, total weight = 6. The optimal strategy is to pick the cheapest child at each OR gate.

Expected Outcome

Optimal value: Min(6) — the minimum total arc weight is 6. There are 4 feasible solutions with 3 distinct weight values (6, 8, 10). The two independent OR choices (v1 and v2) multiply to give 2×2 = 4 solutions.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction connecting to the existing graph
Non-trivial	✅ Pass	Distinct feasibility constraints from existing problems
Correctness	❌ Fail	NP-completeness reduction source misidentified; complexity string is naive brute-force
Well-written	❌ Fail	Schema mixes decision/optimization; missing Expected Outcome section; example too simple

Overall: 1 passed, 0 warnings, 3 failed

---

Usefulness

Fail. The issue describes the problem and its motivation (AI game tree search, AO* algorithm, hierarchical planning), but does not mention any concrete reduction rule connecting this problem to the existing reduction graph. An orphan node -- a problem without any planned reduction to/from an existing problem -- has no value in the reduction graph. The issue must specify at least one planned reduction (e.g., "reduces to ILP", "reduces from 3-SAT", etc.) and ideally link a companion [Rule] issue.

Non-trivial

Pass. The AND/OR graph solution problem has genuinely different feasibility constraints (recursive AND/OR gate satisfaction on a DAG with weighted arcs) from all existing problems in the codebase. It is not a renaming or variant of any existing model.

Correctness

Fail. Two issues:

1. NP-completeness reduction source misidentified. The issue claims NP-completeness "via reduction from X3C" (Exact Cover by 3-Sets). However, Sahni 1974 actually proves NP-completeness via reduction from 3-SAT, not X3C. This is confirmed by the NP-Complete Problems discussion site which explicitly states: "Sahni's paper has a bunch of reductions we've done. This time, he uses 3SAT." The reduction constructs an AND/OR graph from a 3-SAT instance where the root is an AND node with children for variables and clauses, and the formula is satisfiable iff the minimum solution cost equals N.

2. Complexity string is naive brute-force. The complexity string "2^num_arcs" is a trivial brute-force bound (enumerate all arc subsets). The issue states "Best known exact algorithm: O*(2^|A|) by brute-force enumeration" but does not cite any algorithm paper. In fact, the note in the "How to solve" section itself suggests a smarter approach: "enumerate choices for each OR vertex (which child to include) ... this gives O*(product of out-degrees of OR vertices)." For a problem from Garey & Johnson, there may well be better algorithms in the literature. The complexity string should reflect the best known algorithm with a proper citation, not a naive upper bound.

Recommendation: The paper "Revisiting the Complexity of And/Or Graph Solution" (Downey, Fellows, Rosamond, 2012, arXiv:1203.3249) provides parameterized complexity results and may contain tighter algorithmic bounds worth investigating.

Well-written

Fail. Several issues:

1. Decision vs. optimization mismatch. The problem is named MinimumWeightAndOrGraph with the "Minimum" prefix, which per project conventions should use Value = Min<i32> as an optimization problem. However, the schema includes a bound field (maximum total weight K) making it a decision problem. The project convention for Minimum... problems is to omit the bound and let the solver find the minimum. Remove the bound field from the schema.

2. Missing Expected Outcome section. The template requires a separate "Expected Outcome" section stating the optimal solution and its objective value. The example mentions the answer inline ("Minimum weight solution: {(0,1), (0,2), (1,3)} with total weight 6") but this should be in a dedicated section with explicit justification of optimality.

3. Example too simple for round-trip testing. The example has only 1 OR vertex with 2 choices, making a total of 2 feasible solutions (weight 6 and weight 9). The rule of thumb requires at least 2 suboptimal feasible solutions in addition to the optimal one (i.e., at least 3 feasible solutions total). A richer example with multiple OR vertices and more branching would better exercise the AND/OR constraint propagation.

4. Symbol inconsistency. The Definition uses f: V \ Leaves -> {AND, OR} for gate labels, but the Schema uses gate_types: Vec<Option<bool>> with Some(true) = AND, Some(false) = OR, None = leaf. The mapping from math symbols to schema types should be explicit. Also, arc_weights uses i32 but the Definition specifies Z+ (positive integers) -- the schema should note that weights must be positive.

5. Variable count may be wrong. The Variables section says "Count: |A| (one per arc)" and "Per-variable domain: {0, 1}" meaning each arc is included or not. But this does not account for the constraint that the source must be in V'. The variable semantics need clearer specification: are the variables arc-inclusion indicators, and the source inclusion is an implicit constraint?

Recommendations

• Add at least one planned reduction (e.g., a [Rule] MinimumWeightAndOrGraph to ILP issue) to connect this problem to the reduction graph
• Fix the NP-completeness reference: Sahni 1974 reduces from 3-SAT, not X3C
• Remove the bound field and treat this as a pure optimization problem (consistent with Minimum... naming)
• Expand the example to have at least 3 OR vertices to create more feasible solutions
• Research better algorithms beyond naive brute-force for the complexity string

[isPANN]

Converted from decision (bound K) to optimization framing: find a solution subgraph of minimum total arc weight. Removed bound field from schema. Created companion rule issue for X3C reduction.