Exact and Approximate Algorithms for Polytree Learning

ArXi:2605.03622v1 Announce Type: cross Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms.