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

CREATORRobert Ganian, Viktoriia Korchemna
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-10253

Browse the full library · About the Tower of Babel