Parameterized Completeness Results for Bayesian Inference

Hans L. Bodlaender, Nils Donselaar, Johan Kwisthout
Proceedings of The 11th International Conference on Probabilistic Graphical Models, PMLR 186:145-156, 2022.

Abstract

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 $\mathsf{W[1]PP}$ and $\mathsf{XLPP}$, which relate to $\mathsf{W[1]}$ and $\mathsf{XNLP}$ respectively as $\mathsf{PP}$ does to $\mathsf{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v186-bodlaender22a, title = {Parameterized Completeness Results for Bayesian Inference}, author = {Bodlaender, Hans L. and Donselaar, Nils and Kwisthout, Johan}, booktitle = {Proceedings of The 11th International Conference on Probabilistic Graphical Models}, pages = {145--156}, year = {2022}, editor = {Salmerón, Antonio and Rumı́, Rafael}, volume = {186}, series = {Proceedings of Machine Learning Research}, month = {05--07 Oct}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v186/bodlaender22a/bodlaender22a.pdf}, url = {https://proceedings.mlr.press/v186/bodlaender22a.html}, abstract = {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 $\mathsf{W[1]PP}$ and $\mathsf{XLPP}$, which relate to $\mathsf{W[1]}$ and $\mathsf{XNLP}$ respectively as $\mathsf{PP}$ does to $\mathsf{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.} }
Endnote
%0 Conference Paper %T Parameterized Completeness Results for Bayesian Inference %A Hans L. Bodlaender %A Nils Donselaar %A Johan Kwisthout %B Proceedings of The 11th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2022 %E Antonio Salmerón %E Rafael Rumı́ %F pmlr-v186-bodlaender22a %I PMLR %P 145--156 %U https://proceedings.mlr.press/v186/bodlaender22a.html %V 186 %X 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 $\mathsf{W[1]PP}$ and $\mathsf{XLPP}$, which relate to $\mathsf{W[1]}$ and $\mathsf{XNLP}$ respectively as $\mathsf{PP}$ does to $\mathsf{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.
APA
Bodlaender, H.L., Donselaar, N. & Kwisthout, J.. (2022). Parameterized Completeness Results for Bayesian Inference. Proceedings of The 11th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 186:145-156 Available from https://proceedings.mlr.press/v186/bodlaender22a.html.

Related Material