New limits of treewidth-based tractability in optimization

DOI10.1007/S10107-020-01563-5zbMATH Open1489.90204arXiv1807.02551OpenAlexW3085455169MaRDI QIDQ2118087FDOQ2118087

Sebastian Pokutta, Gonzalo Muñoz, Yuri Faenza

Publication date: 22 March 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/1807.02551

zbMATH Keywords

treewidthstructured sparsityapproximations of QCQPssemidefinite extension complexity

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Semidefinite programming (90C22)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphical Models, Exponential Families, and Variational Inference
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Computational Complexity
• Expressing combinatorial optimization problems by linear programs
• Incidence matrices and interval graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Complexity of Finding Embeddings in a k-Tree
• Linear vs. semidefinite extended formulations
• Some optimal inapproximability results
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Quickly excluding a planar graph
• Graph minors. II. Algorithmic aspects of tree-width
• Lifts of Convex Sets and Cone Factorizations
• The Matching Polytope has Exponential Extension Complexity
• Graph Theory
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• S-functions for graphs
• Some \(0/1\) polytopes need exponential size extended formulations
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Positive semidefinite rank
• Graph minors. III. Planar tree-width
• Tree clustering for constraint networks
• A Note on Treewidth in Random Graphs
• A sufficient condition for backtrack-bounded search
• Exponential lower bounds for polytopes in combinatorial optimization
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Average case polyhedral complexity of the maximum stable set problem
• On the extension complexity of combinatorial polytopes
• Tree-width and the Sherali-Adams operator
• Linear-time computation of optimal subgraphs of decomposable graphs
• On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity
• A generalization of extension complexity that captures P
• On Integer Programming and the Branch-Width of the Constraint Matrix
• Extension Complexity, MSO Logic, and Treewidth
• Extended formulation for CSP that is compact for instances of bounded treewidth
• Extension Complexity of Independent Set Polytopes
• On the existence of 0/1 polytopes with high semidefinite extension complexity
• Extension complexity of the correlation polytope
• Polynomial-time self-reducibility: theoretical motivations and practical results^∗
• No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
• Strong reductions for extended formulations
• LP Formulations for Polynomial Optimization Problems
• Parameterized extension complexity of independent set and related problems
• Polynomial Bounds for the Grid-Minor Theorem
• Extension complexities of Cartesian products involving a pyramid
• Demand Queries with Preprocessing

Cited In (3)

• Algorithms and Computation
• New Bounds on the Capacity of Multidimensional Run-Length Constraints
• Forward bounding on pseudo-trees for DCOPs and ADCOPs

This page was built for publication: New limits of treewidth-based tractability in optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118087)