# Exact and Approximate Algorithms for Polytree Learning

arXiv: https://arxiv.org/abs/2605.03622 · HTML: https://mlsanity.com/paper/2605.03622/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 21 references that are in the map.
- First posted on arXiv 5 May 2026.

## Builds on (most cited first, 6 of 6)

- [Learning Polytrees](https://mlsanity.com/paper/1301.6688/) (2013)
- [Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis](https://mlsanity.com/paper/2004.14724/) (2020)
- [Parameterized Complexity Results for Exact Bayesian Network Structure Learning](https://mlsanity.com/paper/1402.0558/) (2014)
- [On the Parameterized Complexity of Polytree Learning](https://mlsanity.com/paper/2105.09675/) (2021)
- [Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings](https://mlsanity.com/paper/2204.02902/) (2022)
- [The Complexity of Bayesian Network Learning: Revisiting the Superstructure](https://mlsanity.com/paper/2602.10253/) (2026)

## Abstract (arXiv)

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.