Reproduce “Optimal Decision Tree Pruning Revisited: Algorithms and Complexity” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Juha Harviainen, Frank Sommer, Manuel Sorge, Stefan Szeider

This research rigorously investigates optimal decision tree pruning operations, providing a comprehensive complexity analysis for subtree replacement and subtree raising. It presents improved polynomial-time algorithms for subtree replacement and establishes NP-completeness and W[1]-hardness for subtree raising under various parameters, demonstrating that existing heuristics achieve near-optimal performance in many practical scenarios.

Key insights

  • Subtree replacement (DTREP) is polynomial-time solvable, with new algorithms achieving O((n + min{k², t²}) \cdot s) runtime, but becomes NP-hard when applied to decision tree ensembles.
  • Subtree raising (DTRAIS) is NP-complete and W[1]-hard for key parameters like the number of pruned nodes (k) and the resulting tree size (ℓ), indicating its inherent computational difficulty.
  • The error reduction in subtree raising is not monotonic, meaning performing more pruning operations does not necessarily guarantee fewer errors, complicating optimization for exact k-node pruning.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.