# Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2020.

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

- [Learning Bayesian Networks in the Presence of Structural Side Information](https://mlsanity.com/paper/2112.10884/) (2021)
- [On the Parameterized Complexity of Polytree Learning](https://mlsanity.com/paper/2105.09675/) (2021)
- [On Projectivity in Markov Logic Networks](https://mlsanity.com/paper/2204.04009/) (2022)
- [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)
- [New Complexity-Theoretic Frontiers of Tractability for Neural Network Training](https://mlsanity.com/paper/2607.20811/) (2026)
- [The Computational Complexity of Concise Hypersphere Classification](https://mlsanity.com/paper/2312.07103/) (2023)
- [Learning the Finer Things: Bayesian Structure Learning at the Instantiation Level](https://mlsanity.com/paper/2303.04339/) (2023)
- [Computing Expected Motif Counts for Exchangeable Graph Generative Models](https://mlsanity.com/paper/2305.01089/) (2023)
- [The Complexity of Optimizing Atomic Congestion](https://mlsanity.com/paper/2312.10219/) (2023)
- [Exact discovery is polynomial for certain sparse causal Bayesian networks](https://mlsanity.com/paper/2406.15012/) (2024)
- [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)

We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the network or its moralized graph are close, in terms of vertex or edge deletions, to a sparse graph class Pi. For example, we show that learning an optimal network whose moralized graph has vertex deletion distance at most k from a graph with maximum degree 1 can be computed in polynomial time when k is constant. This extends previous work that gave an algorithm with such a running time for the vertex deletion distance to edgeless graphs [Korhonen & Parviainen, NIPS 2015]. We then show that further extensions or improvements are presumably impossible. For example, we show that learning optimal networks where the network or its moralized graph have maximum degree 2 or connected components of size at most c, c≥ 3, is NP-hard. Finally, we show that learning an optimal network with at most k edges in the moralized graph presumably has no f(k)· |I|O(1)-time algorithm and that, in contrast, an optimal network with at most k arcs can be computed in 2O(k)· |I|O(1) time where |I| is the total input size.