Parameterized Complexity of Small Decision Tree Learning

Authors

  • Sebastian Ordyniak University of Leeds
  • Stefan Szeider TU Wien

DOI:

https://doi.org/10.1609/aaai.v35i7.16800

Keywords:

Computational Complexity of Reasoning

Abstract

We study the NP-hard problem of learning a decision tree (DT) of smallest depth or size from data. We provide the first parameterized complexity analysis of the problem and draw a detailed parameterized complexity map for the natural parameters: size or depth of the DT, maximum domain size of all features, and the maximum Hamming distance between any two examples. Our main result shows that learning DTs of smallest depth or size is fixed-parameter tractable (FPT) parameterized by the combination of all three of these parameters. We contrast this FPT-result by various hardness results that underline the algorithmic significance of the considered parameters.

Downloads

Published

2021-05-18

How to Cite

Ordyniak, S., & Szeider, S. (2021). Parameterized Complexity of Small Decision Tree Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6454-6462. https://doi.org/10.1609/aaai.v35i7.16800

Issue

Section

AAAI Technical Track on Knowledge Representation and Reasoning