Following [1]},
a series of papers [2]}, [3]}, [4]}, [5]}, [6]} provided algorithms, with provable
guarantees, to build
decision trees that induce explainable clustering.
Several cost functions to guide the clustering construction were investigated as the \(k\) -means, \(k\) -centers, \(k\) -medians and maximum-spacing.
Despite this active research,
the only work on the field that tackles the computational complexity of building explainable clustering
is [7]}, where it was proved that optimizing the
\(k\) -means and the \(k\) -medians cost functions is NP-Complete. Here, we
improve these results and also investigate the computational complexity
for both the \(k\) -centers and the spacing cost functions.
