The Complexity of Bayesian Network Learning: Revisiting the Superstructure
Robert Ganian, Viktoriia Korchemna · 2026
Read The Complexity of Bayesian Network Learning: Revisiting the Superstructure by Robert Ganian, Viktoriia Korchemna (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-10253.txt.
Description
Bayesian Network Structure Learning has drawn wide empirical and theoretical attention, yet its parameterized complexity remains partly unmapped. A 2026 paper by Robert Ganian and Viktoriia Korchemna follows up on superstructure-based analyses of the problem. Where known results suggest the problem is unlikely to be fixed-parameter tractable under vertex-cover size in the superstructure, the authors show a feedback edge set parameterization yields fixed-parameter tractability.
That result strengthens to a localized feedback edge set, with matching lower bounds completing a complexity classification across virtually all well-studied graph parameters. The paper then turns to input representation: where past work assumed a non-zero representation, an additive representation makes the problem fixed-parameter tractable under far milder superstructure restrictions, notably treewidth alone. The results extend to the closely related Polytree Learning problem.
Catalog record
| CREATOR | Robert Ganian, Viktoriia Korchemna |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 140 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-10253