# The Complexity of Bayesian Network Learning: Revisiting the Superstructure

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 62 references that are in the map.
- First posted on arXiv 10 Feb 2026.

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

- [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)
- [Parameterized Algorithms for the Matrix Completion Problem](https://mlsanity.com/paper/1804.03423/) (2018)
- [Refined Complexity of PCA with Outliers](https://mlsanity.com/paper/1905.04124/) (2019)
- [On the Parameterized Complexity of Polytree Learning](https://mlsanity.com/paper/2105.09675/) (2021)
- [The Complexity Landscape of Decompositional Parameters for ILP](https://mlsanity.com/paper/1809.00585/) (2018)
- [On Structural Parameterizations of the Edge Disjoint Paths Problem](https://mlsanity.com/paper/1711.02076/) (2017)
- [The Power of Cut-Based Parameters for Computing Edge Disjoint Paths](https://mlsanity.com/paper/1808.03496/) (2018)
- [Algorithmic Applications of Tree-Cut Width](https://mlsanity.com/paper/2206.00752/) (2022)
- [Parameterized algorithms and data reduction for the short secluded s-t-path problem](https://mlsanity.com/paper/1806.09540/) (2018)
- [Parameterized Complexity of Min-Power Asymmetric Connectivity](https://mlsanity.com/paper/2005.14620/) (2020)

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

- [New Complexity-Theoretic Frontiers of Tractability for Neural Network Training](https://mlsanity.com/paper/2607.20811/) (2026)
- [Exact and Approximate Algorithms for Polytree Learning](https://mlsanity.com/paper/2605.03622/) (2026)

## Abstract (arXiv)

We investigate the parameterized complexity of Bayesian Network Structure Learning (BNSL), a classical problem that has received significant attention in empirical but also purely theoretical studies. We follow up on previous works that have analyzed the complexity of BNSL w.r.t. the so-called superstructure of the input. While known results imply that BNSL is unlikely to be fixed-parameter tractable even when parameterized by the size of a vertex cover in the superstructure, here we show that a different kind of parameterization - notably by the size of a feedback edge set - yields fixed-parameter tractability. We proceed by showing that this result can be strengthened to a localized version of the feedback edge set, and provide corresponding lower bounds that complement previous results to provide a complexity classification of BNSL w.r.t. virtually all well-studied graph parameters. We then analyze how the complexity of BNSL depends on the representation of the input. In particular, while the bulk of past theoretical work on the topic assumed the use of the so-called non-zero representation, here we prove that if an additive representation can be used instead then BNSL becomes fixed-parameter tractable even under significantly milder restrictions to the superstructure, notably when parameterized by the treewidth alone. Last but not least, we show how our results can be extended to the closely related problem of Polytree Learning.