# On the Parameterized Complexity of Polytree Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 36 references that are in the map.
- First posted on arXiv 20 May 2021.

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

- [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)
- [Turbocharging Treewidth-Bounded Bayesian Network Structure Learning](https://mlsanity.com/paper/2006.13843/) (2020)
- [On the Relation of Strong Triadic Closure and Cluster Deletion](https://mlsanity.com/paper/1803.00807/) (2018)
- [Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms](https://mlsanity.com/paper/1304.4626/) (2013)
- [Deterministic Truncation of Linear Matroids](https://mlsanity.com/paper/1404.4506/) (2014)

## Built on by (most cited first, 6 of 6)

- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [The Complexity of Bayesian Network Learning: Revisiting the Superstructure](https://mlsanity.com/paper/2602.10253/) (2026)
- [Learning Linear Gaussian Polytree Models with Interventions](https://mlsanity.com/paper/2311.04636/) (2023)
- [The Complexity of Optimizing Atomic Congestion](https://mlsanity.com/paper/2312.10219/) (2023)
- [Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy](https://mlsanity.com/paper/2511.08091/) (2025)
- [Exact and Approximate Algorithms for Polytree Learning](https://mlsanity.com/paper/2605.03622/) (2026)

## Abstract (arXiv)

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. textscPolytree Learning 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 textscPolytree Learning. We show that textscPolytree Learning can be solved in 3n · |I|O(1) time where n is the number of variables and |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 textscPolytree Learning. We show that textscPolytree Learning has no f(d)· |I|O(1)-time algorithm, unlike Bayesian network learning which can be solved in 2d · |I|O(1) time. We show that, in contrast, if d and the maximum parent set size are bounded, then we can obtain efficient algorithms.