2026/05/05 by Juha Harviainen, Frank Sommer, Manuel Sorge · 1 voice
Computer Science · #cs.CC #cs.DS #cs.LG
paper · pdf · doi:10.48550/arxiv.2605.03622
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 more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time O((2+ε)n) for arbitrarily small ε> 0 and any constant in-degree bound k, improving over the fastest previously known algorithm of time complexity O(3n). We further give polynomial-time algorithms for finding a polytree whose score is within a factor of k from the optimal one for arbitrary scores and a factor of 2 for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.