Parameterized exact fair decision tree learning with small sensitive group regimes

Fairness-constrained tree learning is highly desirable for high-accountability settings; however, exact combinatorial optimization is often considered computationally impractical when fairness constraints are strictly enforced. While most existing fair classification methods rely on heuristic reductions or surrogate losses, exact tree studies primarily focus on unconstrained predictive accuracy. In this paper, we propose a memoized exact-search framework for decision trees under explicit statistical-parity constraints and provide a parameterized analysis of its runtime with respect to sensitive-group cardinality. Through comprehensive evaluations—including scalability checks, caching ablations, controlled CART comparisons, benchmark repeats, and validation on real-world datasets—we demonstrate that the proposed method preserves exactness while significantly mitigating redundant computations. Our results reveal that exact fair optimization remains practically viable for scenarios with small sensitive-group regimes. Under a 10-repeat shared held-out testing protocol, memoized exact search improves test accuracy over full-training CART, same-120-subset CART, and a demographic-parity reduction baseline using depth-3 CART, while test-set statistical-parity differences remain comparable in magnitude and training-set feasibility is maintained. These findings highlight a concrete trade-off between runtime, accuracy, and parity control for small encoded optimization subsets.