Complexity of Inference in Graphical Models
Venkat Chandrasekaran, Nathan Srebro, Prahladh Harsha
It is well-known that inference in graphical models is hard in the worst case, but tractable for models with bounded treewidth. We ask whether treewidth is the only structural criterion of the underlying graph that enables tractable inference. In other words, is there some class of structures with unbounded treewidth in which inference is tractable? Subject to a combinatorial hypothesis due to Robertson et al. (1994), we show that low treewidth is indeed the only structural restriction that can ensure tractability. Thus, even for the ?best case? graph structure, there is no inference algorithm with complexity polynomial in the treewidth.
PDF Link: /papers/08/p70-chandrasekaran.pdf
AUTHOR = "Venkat Chandrasekaran
and Nathan Srebro and Prahladh Harsha",
TITLE = "Complexity of Inference in Graphical Models",
BOOKTITLE = "Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2008",
PAGES = "70--78"