New limits of treewidth-based tractability in optimization
- PDF / 526,117 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 175 Views
Series A
New limits of treewidth-based tractability in optimization Yuri Faenza1 · Gonzalo Muñoz2
· Sebastian Pokutta3,4
Received: 20 March 2019 / Accepted: 2 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
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 on extension complexity based 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 in Graphical Models in Machine Learning and in Constraint Satisfaction Problems, which here we extend to an approximation setting in Optimization. Keywords Treewidth · Structured sparsity · Semidefinite extension complexity · Approximations of QCQPs Mathematics Subject Classification 90C05 · 90C22 · 90C35
B
Gonzalo Muñoz [email protected] Yuri Faenza [email protected] Sebastian Pokutta [email protected]
1
Industrial Engineering and Operations Research, Columbia University, New York, USA
2
Institute of Engineering Sciences, Universidad de O’Higgins, Rancagua, Chile
3
Zuse Institute Berlin, Berlin, Germany
4
Department of Mathematics, Technische Universität Berlin, Berlin, Germany
123
Y. Faenza et al.
1 Introduction Treewidth is a graph-theoretical parameter used to measure, roughly speaking, how far a graph is from being a tree. It was explicitly defined by Robertson and Seymour [53] (also see [54]), but there are many equivalent definitions. An earlier discussion is found in [41] and closely related concepts have been used by many authors under different names, e.g., the “running intersection” property, and the notion of “partial k-trees”. Here we will use the following definition; recall that a chordal graph is a graph where every induced cycle has exactly three vertices. Definition 1 An undirected graph G = (V , E) has treewidth ≤ ω if there exists a chordal graph H = (V , E ) with E ⊆ E and clique number ≤ ω + 1. We denote as tw(G) the treewidth of G. Note that H in the definition above is sometimes referred to as a chordal completion of G. It can be shown that a graph has treewidth 1 if and only if it is a forest. On the other extreme, a complete graph of n vertices has tre
Data Loading...
