New limits of treewidth-based tractability in optimization

Abstract

Sparse structures are frequently sought when pursuing tractability in optimization problems. They are exploited from both theoretical and computational perspectives to handle complex problems that become manageable when sparsity is present. An example of this type of structure is given by treewidth: a graph theoretical parameter that measures how tree-like a graph is. This parameter has been used for decades for analyzing the complexity of various optimization problems and for obtaining tractable algorithms for problems where this parameter is bounded. The goal of this work is to contribute to the understanding of the limits of the treewidth-based tractability in optimization. Our results are as follows. First, we prove that, in a certain sense, the already known positive results onextension complexitybased on low treewidth are the best possible. Secondly, under mild assumptions, we prove that treewidth is the only graph-theoretical parameter that yields tractability for a wide class of optimization problems, a fact well known inGraphical Modelsin Machine Learning and inConstraint Satisfaction Problems, which here we extend to an approximation setting inOptimization.