TL;DR: This is an informal summary of our recent paper Limits of Treewidth-based tractability in Optimization with Yuri Faenza and Gonzalo Muñoz, where we provide almost matching lower bounds for extended formulations that exploit small treewidth to obtain smaller formulations. We also show that treewidth in some sense is the only graph-theoretic notion that appropriately captures sparsity and tractability in a broader algorithmic setting.

What is the paper about and why you might care

It it well known that for many problems on graphs, e.g., optimization problems but also problems in the context of graphical models, that are hard to solve in full generality, we can obtain fast algorithms if the underlying graph $G$ exhibits small treewidth. Without going into detail here, treewidth basically measures how close a graph is to a tree and it has been extensively used as a concept to model and capture sparsity in problems. Typically, we can obtain then algorithms that have a running time that is super-polynomial in the treewidth but polynomial in the problem dimension, where the notion of dimension depends on the context. One such example is combinatorial problems on graphs, where Dynamic Programming can be used to obtain fast algorithms (with a non-polynomial dependence on the treewidth); we refer the interested reader to the actual paper for an extensive list of references. As such one might think of treewidth as a complexity parameter leading to some form of parametrized complexity.

It is also known, that such problems often admit linear programming formulations or semidefinite programming formulation parametrized by treewidth (e.g., via Sherali-Adams and Lasserre hierarchy approaches). More recently a very comprehensive result in [BM] by Bienstock and Muñoz extended this to the general case of mixed-integer polynomial optimization basically showing the following:

Theorem (informal) [Bienstock and Muñoz]. Consider a polynomial optimization problem of the form where $f_i(x)$ are polynomials of degree at most $\rho$. If the underlying constraint intersection graph $\Gamma$ (the graph that has a vertex for each variable of the problem and an edge between two variables if they appear in a common constraint) has treewidth at most $\omega$, then there is a linear program of size $O((2\rho/\varepsilon)^{\omega + 1}n \log 1/\varepsilon)$ that computes an $\varepsilon$-approximate solution to the polynomial optimization problem.

This basically matches the type of bounds that have been obtained beforehand for other types of problems. With this a couple of natural questions arise:

  1. Are these bounds of the form of $O(n 2^\omega)$ the best one can hope for, for linear or semidefinite programming formulations?
  2. Are there other graph-theoretic concepts of sparsity apart from treewidth that can be used similarly to obtain parametrized complexity measures?

Our results

We basically answer both of those questions from above. It is important to point out though that the results for linear programming or semidefinite programming are somewhat different from the algorithmic ones: the algorithmic statements holds for general algorithms but are conditional on the usual $\operatorname{P} \neq \operatorname{NP}$ assumption (and in fact we use the complexity-theoretic assumption $\operatorname{NP} \not\subseteq \operatorname{BPP}$), the linear programming and semidefinite programming statements hold unconditionally but only apply to those two optimization paradigms.

First we show that, there is no other graph-theoretic structure that yields tractability in the same way as treewidth does (for optimization problems). In a nutshell:

Unbounded treewidth can yield intractability.

This result relies on the commonly believed complexity-theoretic assumption $\operatorname{NP} \not\subseteq \operatorname{BPP}$ and the grid-minor hypothesis that was recently shown to be true in a breakthrough result in [CC] by Chekuri and Chuzhoy. Our proof works via a reduction and is the analog of a similar result known in graphical models; see Chandrasekaran et al. [CSH].

Second we show that, the upper bounds as parametrized by treewidth obtained for linear programming formulations as well as semidefinite formulations are essentially optimal (with minor losses):

Linear programming and semidefinite programming formulations of size of the form $O(n 2^\omega)$ are basically the best one can hope for.

Finally, I would also like to mention that independent of our work Aboulker et al. showed in [A+] a similar result for the linear extension complexity case based on analyzing faces of the correlation polytope.


[FMP] Faenza, Y., Muñoz, G., & Pokutta, S. (2018). Limits of Treewidth-based tractability in Optimization. arXiv preprint arXiv:1807.02551. arxiv

[BM] Bienstock, D., & Mun͂oz, G. (2018). LP Formulations for Polynomial Optimization Problems. SIAM Journal on Optimization, 28(2), 1121-1150. journal arxiv

[CC] Chekuri, C., & Chuzhoy, J. (2016). Polynomial bounds for the grid-minor theorem. Journal of the ACM (JACM), 63(5), 40. journal arxiv

[CSH] Chandrasekaran, V., Srebro, N., & Harsha, P. (2012). Complexity of inference in graphical models. arXiv preprint arXiv:1206.3240. arxiv

[A+] Aboulker, P., Fiorini, S., Huynh, T., Macchia, M., & Seif, J. (2018). Extension Complexity of the Correlation Polytope. arXiv preprint arXiv:1806.00541. arxiv