Proceedings

Inapproximability of Treewidth and Related Problems (Extended Abstract)

Yu Wu, Per Austrin, Toniann Pitassi, David Liu

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Journal Track. Pages 4222-4227.

Abstract

Graphical models, such as Bayesian Networks and Markov networks play an important role in artificial intelligence and machine learning. Inference is a central problem to be solved on these networks. This, and other problems on these graph models are often known to be hard to solve in general, but tractable on graphs with bounded Treewidth. Therefore, finding or approximating the Treewidth of a graph is a fundamental problem related to inference in graphical models. In this paper, we study the approximability of a number of graph problems: Treewidth and Pathwidth of graphs, Minimum Fill-In, and a variety of different graph layout problems such as Minimum Cut Linear Arrangement. We show that, assuming Small Set Expansion Conjecture, all of these problems are NP-hard to approx- imate to within any constant factor in polynomial time.

Yu Wu, Per Austrin, Toniann Pitassi, and David Liu. 2015. Inapproximability of Treewidth and Related Problems (Extended Abstract). In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 4222–4227. https://ijcai.org/proceedings/2015/600
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards