[Model] MinimumDecisionTree

[isPANN]

Motivation

MINIMUM DECISION TREE (MS15) from Garey & Johnson, A1.2. Given a set of objects distinguished by binary tests, find a decision tree that identifies each object with minimum total external path length (the weighted sum of test depths for identifying each object). NP-hard even when each test has at most 3 objects with value 1 (Hyafil and Rivest 1976). The problem captures optimal test sequencing for identification — applications in medical diagnosis, fault isolation, species classification, and information-theoretic search.

Definition

Name: MinimumDecisionTree
Reference: Garey & Johnson, Computers and Intractability, A1.2 MS15; Hyafil and Rivest 1976

Mathematical definition:

INSTANCE: Set S of objects, collection T = {T_1, T_2, ..., T_m} of binary tests, where each test T_j is a function from S into {0,1}, such that for every pair of objects s, s' ∈ S there exists a test T_j ∈ T with T_j(s) ≠ T_j(s').
OBJECTIVE: Find a decision tree using tests from T that identifies each member of S and minimizes the total external path length.

A decision tree is a binary tree where each internal node is labeled by a test T_j. The left child corresponds to outcome 0 and the right child to outcome 1. Each leaf is labeled by an object. The external path length of a leaf is the number of edges from the root to that leaf. The total external path length is the sum over all leaves.

Variables

• Count: The tree structure is the decision variable. Equivalently, one can encode the tree as a sequence of test selections at each internal node.
• Per-variable domain: Each internal node chooses from {T_1, ..., T_m}.
• Meaning: The assignment of tests to internal nodes of a binary tree. The tree must correctly distinguish all objects, and the objective is to minimize the total external path length.

Schema (data type)

Type name: MinimumDecisionTree
Variants: none (unique input structure)

Field	Type	Description
test_matrix	Vec<Vec<bool>>	Binary matrix: test_matrix[j][i] = true iff object i passes test j
num_objects	usize	Number of objects
num_tests	usize	Number of tests

Complexity

• Best known exact algorithm: O*(num_tests^num_objects) by enumerating all possible decision trees. NP-hard even when each test has at most 3 objects with value 1 (Hyafil and Rivest 1976; transformation from EXACT COVER BY 3-SETS).
• Complexity string: "num_tests^num_objects"

Extra Remark

Full book text:

INSTANCE: Set S of "objects," collection T = {T_1, T_2, ..., T_m} of "binary tests," where each test T_j is a function from S into {0,1}, such that for every pair of objects s, s' ∈ S there exists a test T_j ∈ T with T_j(s) ≠ T_j(s'), positive integer K.
QUESTION: Is there a decision tree for T that "identifies" each member of S and has total external path length of at most K?

Reference: [Hyafil and Rivest, 1976]. Transformation from EXACT COVER BY 3-SETS.
Comment: NP-complete even if each test T_j has at most 3 objects s ∈ S for which T_j(s) = 1.

Note: The original G&J formulation is a decision problem with threshold K. We use the equivalent optimization formulation: minimize total external path length.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all binary trees with test labels at internal nodes; prune those that don't identify all objects; return minimum total path length.)
• It can be solved by reducing to integer programming.
• Other:

Reduction Rule Crossref

(Planned: ExactCoverBy3Sets → MinimumDecisionTree, following Hyafil & Rivest 1976)

Example Instance

Input:
Objects: S = {o0, o1, o2, o3} (4 objects).
Tests:

       o0  o1  o2  o3
T0:     1   1   0   0
T1:     1   0   0   0
T2:     0   1   0   1

Each pair of objects is distinguished by at least one test:
(o0,o1): T1,T2; (o0,o2): T0,T1; (o0,o3): T0,T1,T2; (o1,o2): T0,T2; (o1,o3): T0; (o2,o3): T2.

Optimal decision tree (total path length = 8):

        T0
       /  \
    (0)    (1)
    T2      T1
   /  \    /  \
  o2   o3  o1  o0

• Root: test T0. Left (T0=0): objects {o2, o3}. Right (T0=1): objects {o0, o1}.
• Left child: test T2. T2(o2)=0 → leaf o2 (depth 2). T2(o3)=1 → leaf o3 (depth 2).
• Right child: test T1. T1(o1)=0 → leaf o1 (depth 2). T1(o0)=1 → leaf o0 (depth 2).
• Total path length = 2+2+2+2 = 8. ✓

Suboptimal decision tree (total path length = 9):

        T1
       /    \
    (0)      (1)
     T0      o0
    /  \
  T2    o1
 /  \
o2   o3

• Root: test T1. T1(o0)=1 → leaf o0 (depth 1). T1=0: objects {o1, o2, o3}.
• T0 on {o1,o2,o3}: T0(o1)=1 → leaf o1 (depth 2). T0=0: objects {o2, o3}.
• T2 on {o2,o3}: T2(o2)=0 → leaf o2 (depth 3). T2(o3)=1 → leaf o3 (depth 3).
• Total path length = 1+2+3+3 = 9.

Why the balanced tree wins: Starting with T1 (which isolates only o0) gives depth 1 for o0 but pushes three objects deeper. The balanced split by T0 (2-2) yields uniform depth 2 for all objects, achieving the minimum total path length.

Expected Outcome

Optimal value: Min(8) — the minimum total external path length is 8. There are 6 valid decision trees with 2 distinct path lengths: 4 trees with PL=8 and 2 trees with PL=9.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction connecting this problem to the existing graph
Non-trivial	✅ Pass	Distinct problem with unique feasibility constraints
Correctness	⚠️ Warn	Complexity bound is naive brute-force, not a best-known algorithm
Well-written	❌ Fail	Example contains contradictory K value; missing Expected Outcome section

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The problem DecisionTree does not yet exist in the codebase — confirmed via pred show DecisionTree. However, the issue body mentions no planned reduction rules connecting this problem to the existing reduction graph. There is no "Reduction Rule Crossref" section and no mention of any reduction to/from an existing problem (e.g., ExactCoverBy3Sets, ILP, or any other problem). A problem without any planned reduction rule is an orphan node with no value in the reduction graph.

To fix: Add at least one concrete planned reduction rule (e.g., ExactCoverBy3Sets → DecisionTree following Hyafil & Rivest's original NP-completeness proof, or a direct DecisionTree → ILP formulation).

Non-trivial

The Decision Tree (identification) problem has genuinely distinct feasibility constraints from all 126 existing problems. It requires constructing a binary tree structure where internal nodes are labeled with tests, leaves correspond to unique objects, and the objective is to minimize total external path length. This is not a repackaging of any existing graph, formula, set, or algebraic problem.

Verdict: Pass.

Correctness

Reference verification:

• Hyafil and Rivest 1976 — Confirmed real. "Constructing Optimal Binary Decision Trees is NP-Complete," Information Processing Letters, Vol. 5, No. 1, pp. 15–17, May 1976. Available at MIT CSAIL. The paper proves NP-completeness via reduction from EXACT COVER BY 3-SETS, and confirms that the problem remains NP-complete even when each test has at most 3 objects with value 1.
• Garey & Johnson A1.2 MS15 — Consistent with the standard reference.
• Mathematical definition — The formal definition matches the G&J formulation correctly (verified against the "Extra Remark" full book text).

Complexity concern: The issue claims a "best known exact algorithm" of O*(m^n) (i.e., num_tests^num_objects), but this is simply naive enumeration of all possible decision trees. This is not a researched best-known algorithm — it is a trivial brute-force upper bound. For a well-studied NP-complete problem from 1976, there may be better exact algorithms (e.g., dynamic programming approaches). The issue should cite a specific algorithm paper or acknowledge this is a naive bound.

Well-written

Failures:

1. Example contains contradictory K value. The heading says "Optimal decision tree with K = 6" but the worked example shows a total external path length of 8 (four leaves each at depth 2). Then it says "With K = 8, the answer is YES. With K = 7, the answer is NO." The K = 6 in the heading is wrong and contradicts the actual computation.

2. Missing Expected Outcome section. The template requires a clear expected outcome: for a satisfaction problem, this means stating a concrete satisfying solution (or lack thereof) with the given threshold K. The example does eventually state YES/NO for different K values, but this is buried in narrative rather than presented as a clear expected outcome.

3. Missing planned reductions / How to solve gap. Only bruteforce is checked. No ILP path is identified, and no reduction crossref section exists. While bruteforce alone is acceptable, the complete absence of any reduction mention (even planned ones) is a gap.

4. Complexity string lacks citation. The complexity expression num_tests^num_objects is presented without citing a specific algorithm or paper — it is just a naive enumeration bound, not a researched result.

Warnings:

• The schema uses Vec<Vec<bool>> for test_matrix which is fine for the stated domain, but the field num_objects and num_tests are redundant with the matrix dimensions. This is a minor design concern (not a failure).

Recommendations

• The original NP-completeness proof (Hyafil & Rivest 1976) reduces from EXACT COVER BY 3-SETS. This would be a natural [Rule] companion issue.
• Consider whether a direct DecisionTree → ILP formulation is feasible (binary variables for test assignments at each node, flow constraints for object routing).
• For the complexity string, consider researching dynamic programming approaches. Adler and Heeringa (2012) "Approximating Optimal Binary Decision Trees" and related work may provide tighter bounds.

[isPANN]

Converted from decision framing (DecisionTree with bound K) to optimization framing (MinimumDecisionTree — minimize total external path length). Removed Useless and PoorWritten labels. Companion rule issue to follow: ExactCoverBy3Sets → MinimumDecisionTree (G&J R337).

[isPANN]

Fix-issue changelog

• Example: replaced trivial 2-test example (4 objects, only 1 possible path length) with 3-test example (6 valid trees, 2 distinct path lengths 8 and 9); drew both optimal (balanced, PL=8) and suboptimal (unbalanced, PL=9) tree structures; explained why balanced split wins
• Expected Outcome: added section with Min(8) and tree/PL distribution
• Reduction Crossref: added planned ExactCoverBy3Sets → MinimumDecisionTree (Hyafil & Rivest 1976)
• Fixed contradictory K value from original example (heading said K=6 but computation showed 8)

Applied by /fix-issue.