Parameterized Completeness Results for Bayesian Inference

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


We present completeness results for inference in Bayesian networks with respect to two different parameterizations, namely the number of variables and the topological vertex separation number. For this we introduce the parameterized complexity classes W[1]PP and XLPP, which relate to W[1] and XNLP respectively as PP does to NP. The second parameter is intended as a natural translation of the notion of pathwidth to the case of directed acyclic graphs, and as such it is a stronger parameter than the more commonly considered treewidth. Based on a recent conjecture, the completeness results for this parameter suggest that deterministic algorithms for inference require exponential space in terms of pathwidth and by extension treewidth. These results are intended to contribute towards a more precise understanding of the parameterized complexity of Bayesian inference and thus of its required computational resources in terms of both time and space.
Original languageEnglish
Title of host publicationInternational Conference on Probabilistic Graphical Models, PGM 2022, 5-7 October 2022, Almería, Spain
EditorsAntonio Salmerón, Rafael Rumí
Number of pages12
Publication statusPublished - 19 Sept 2022

Publication series

NameProceedings of Machine Learning Research


  • Bayesian networks
  • inference
  • parameterized complexity theory


Dive into the research topics of 'Parameterized Completeness Results for Bayesian Inference'. Together they form a unique fingerprint.

Cite this