Research map / Learning theory and algorithms / Combinatorial and search optimization

Learning Small Decision Trees for Data of Low Rank-Width

AAAI 2024 · Learning theory and algorithms › Combinatorial and search optimization · approach: Structure and complexity of constraint reasoning · 3 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that finding a smallest decision tree for a classification instance is fixed-parameter tractable parameterized by the rank-width (NLC-width) of its incidence graph, via leaf-to-root dynamic programming over NLC-expression trees with succinct DT skeleton records.

Problem

Finding a smallest decision tree consistent with a partially defined Boolean function (classification instance) is NP-hard; the paper seeks tractability under a structural parameter of the instance's incidence graph.

Approach

Replace novel and old features by future/forgotten feature placeholders along an NLC-expression tree, compress partial solutions into reduced DT skeletons with contraction operations, and run a DP over records (skeleton, size) whose count is bounded in terms of k.

Key results

• DTS (minimum decision tree size) is fixed-parameter tractable parameterized by NLC-width, and hence by rank-width of the incidence graph.
• Running time is O(2^{3k+1}(2^k+2^k)^{2^{3k+2}+1} · k|E ∪ feat(E)|) for the join-node dominated DP.
• Rank-width is domination-equivalent to renamable rank-width and strictly dominates renamable treewidth.

Surprising findings

• Rank-width strictly dominates renamable treewidth, which itself strictly dominates treewidth, so the result generalizes treewidth-based tractability.

Limitations

• Algorithm is FPT but the running time is a very large function of k (doubly exponential in k), so practicality is unclear.
• Does not address decision trees of small depth; only an XP algorithm is obtained for depth.
• Only handles Boolean features; non-Boolean ordered domains are not covered unless domains are bounded.

Experimental setup

Builds on: NLC-width (Wanke 1994) Ordyniak and Szeider 2021 parameterized DT size

Closest papers by meaning

• Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.89)
• Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.89)
• Witty: An Efficient Solver for Computing Minimum-Size Decision Trees (AAAI 2025 · similarity 0.89)
• Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.87)
• Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.86)
• Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms (ICML 2025 · similarity 0.85)