The influence of dimensions on the complexity of computing decision trees

Stephen Kobourov; Maarten Löffler; Fabrizio Montecchiani; Marcin Pilipczuk; Ignaz Rutter; Raimund Seidel; Manuel Sorge; Jules Wulms

doi:10.1016/j.artint.2025.104322

The influence of dimensions on the complexity of computing decision trees

Stephen Kobourov, Maarten Löffler, Fabrizio Montecchiani^*, Marcin Pilipczuk, Ignaz Rutter, Raimund Seidel, Manuel Sorge, Jules Wulms

^*Corresponding author for this work

Sub Geometric Computing

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

A decision tree recursively splits a feature space R^d and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space R^d, which contains n training examples. We show that it can be solved in O(n^2d+1) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f(d)⋅n^o(d/log⁡d) running time. The problem is solvable in (dR)^O(dR)⋅n^1+o(1) time if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

Original language	English
Article number	104322
Journal	Artificial Intelligence
Volume	343
DOIs	https://doi.org/10.1016/j.artint.2025.104322
Publication status	Published - Jun 2025

Bibliographical note

Publisher Copyright:
© 2025 The Author(s)

Funding

Main ideas for the results of this paper were developed in the relaxed atmosphere of Dagstuhl Seminar 21062 on Parameterized Complexity in Graph Drawing, organized by Robert Ganian, Fabrizio Montecchiani, Martin Noellenburg, and Meirav Zehavi. An extended abstract of this work appeared at AAAI 2023 [18] . In comparison, this version contains full proof details and more discussion. Stephen Kobourov acknowledges funding by the National Science Foundation, grant number NSF-CCF-2212130. Fabrizio Montecchiani acknowledges funding by MUR of Italy, under PRIN Project n. 2022ME9Z78-NextGRAAL: Next-generation algorithms for constrained GRAph visuALization, and by University of Perugia, Fondi di Ricerca di Ateneo, edizione 2022, project MiRA: Mixed Reality and AI Methodologies for Immersive Robotics. Manuel Sorge acknowledges funding by the Alexander von Humboldt Foundation. Jules Wulms acknowledges funding by the Vienna Science and Technology Fund (WWTF) under grant ICT19-035.

Funders	Funder number
National Science Foundation	NSF-CCF-2212130
MUR of Italy	2022ME9Z78-NextGRAAL
University of Perugia, Fondi di Ricerca di Ateneo, edizione 2022, project MiRA: Mixed Reality and AI Methodologies for Immersive Robotics
Alexander von Humboldt Foundation
Vienna Science and Technology Fund (WWTF)	ICT19-035

Keywords

Decision trees
Machine learning
Parameterized complexity

Access to Document

10.1016/j.artint.2025.104322Licence: CC BY

1-s2.0-S0004370225000414-mainFinal published version, 1 MBLicence: CC BY

Cite this

@article{eae272290227407e9f0e14d34fc3ac05,

title = "The influence of dimensions on the complexity of computing decision trees",

abstract = "A decision tree recursively splits a feature space Rd and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space Rd, which contains n training examples. We show that it can be solved in O(n2d+1) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f(d)⋅no(d/log⁡d) running time. The problem is solvable in (dR)O(dR)⋅n1+o(1) time if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.",

keywords = "Decision trees, Machine learning, Parameterized complexity",

author = "Stephen Kobourov and Maarten L{\"o}ffler and Fabrizio Montecchiani and Marcin Pilipczuk and Ignaz Rutter and Raimund Seidel and Manuel Sorge and Jules Wulms",

note = "Publisher Copyright: {\textcopyright} 2025 The Author(s)",

year = "2025",

month = jun,

doi = "10.1016/j.artint.2025.104322",

language = "English",

volume = "343",

journal = "Artificial Intelligence",

issn = "0004-3702",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - The influence of dimensions on the complexity of computing decision trees

AU - Kobourov, Stephen

AU - Löffler, Maarten

AU - Montecchiani, Fabrizio

AU - Pilipczuk, Marcin

AU - Rutter, Ignaz

AU - Seidel, Raimund

AU - Sorge, Manuel

AU - Wulms, Jules

PY - 2025/6

Y1 - 2025/6

N2 - A decision tree recursively splits a feature space Rd and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space Rd, which contains n training examples. We show that it can be solved in O(n2d+1) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f(d)⋅no(d/log⁡d) running time. The problem is solvable in (dR)O(dR)⋅n1+o(1) time if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

AB - A decision tree recursively splits a feature space Rd and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space Rd, which contains n training examples. We show that it can be solved in O(n2d+1) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f(d)⋅no(d/log⁡d) running time. The problem is solvable in (dR)O(dR)⋅n1+o(1) time if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

KW - Decision trees

KW - Machine learning

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=85219733253&partnerID=8YFLogxK

U2 - 10.1016/j.artint.2025.104322

DO - 10.1016/j.artint.2025.104322

M3 - Article

AN - SCOPUS:85219733253

SN - 0004-3702

VL - 343

JO - Artificial Intelligence

JF - Artificial Intelligence

M1 - 104322

ER -

The influence of dimensions on the complexity of computing decision trees

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this