MINIMUM DECISION TREE

• INSTANCE: Finite set X of objects, collection $T=\{T_{1},T_{2},\ldots,T_{m}\}$ of binary tests $T_{i}:X \rightarrow \{0,1\}$.

• SOLUTION: A decision tree t for X using the tests in T, where a decision tree is a binary tree in which each non-leaf vertex is labelled by a test from T, each leaf is labelled by an object from X, the edge from a non-leaf vertex to its left son is labelled 0 and the one to its right son is labelled 1, and, if $T_{i_{1}},O_{i_{1}},T_{i_{2}},O_{i_{2}}, \ldots, T_{i_{k}},O_{i_{k}}$ is the sequence of vertex and edge labels on the path from the root to a leaf labelled by $x\in X$, then x is the unique object for which $T_{i_{j}}(x)=O_{i_{j}}$ for all j, $1\leq j\leq k$.

• MEASURE: Number of leaves of t.

  
  

• Bad News: APX-hard [233].

• Comment: Not approximable within $2^{\log^{(1-\varepsilon )}\vert X\vert}$ unless $NP\subseteq \mbox{\sc QP}$ [233].

• Garey and Johnson: MS15