Tractable Explaining of Multivariate Decision Trees

We study multivariate decision trees (MDTs), in particular,

classes of MDTs determined by the language

of relations that can be used to split feature space.

An abductive explanation (AXp) of the classification

of a particular instance, viewed as a set of feature-value

assignments, is a minimal subset of the instance

which is sufficient to lead to the same decision.

We investigate when finding a single AXp is

tractable. We identify tractable languages for real,

integer and boolean features. Indeed, in the case

of boolean languages, we provide a P/NP-hard dichotomy.