On the Parameterized Complexity of Polytree Learning

A Bayesian network is a directed acyclic graph that represents statistical dependencies between variables of a joint probability distribution. A fundamental task in data science is to learn a Bayesian network from observed data. $\text{textsc}PolytreeLearning$ is the problem of learning an optimal Bayesian network that fulfills the additional property that its underlying undirected graph is a forest. In this work, we revisit the complexity of \textsc{Polytree Learning}. We show that $\text{textsc}PolytreeLearning$ can be solved in $3^n \cdot |I|^{$\mathcal{O}$(1)}$timewhere$n$isthenumberofvariablesand$|I|$ is the total instance size. Moreover, we consider the influence of the number of variables $d$ that might receive a nonempty parent set in the final DAG on the complexity of $\text{textsc}PolytreeLearning$. We show that \textsc{Polytree Learning} has no $f(d)\cdot \mathrm{\mid }I{\mathrm{\mid }}^{\mathcal{O}(1)}$-time algorithm, unlike Bayesian network learning which can be solved in $2^d \cdot |I|^{$\mathcal{O}$(1)}$time\mathrm{.}Weshowthat,incontrast,if$d$ and the maximum parent set size are bounded, then we can obtain efficient algorithms.