Extended formulation for CSP that is compact for instances of bounded treewidth

zbMath1393.68073arXiv1502.05361MaRDI QIDQ907218

Martin Koutecký, Petr Kolman

Publication date: 25 January 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingtreewidthconstraint satisfaction problemsparameterized complexityextended formulations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Unnamed Item ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ Extended formulations for vertex cover ⋮ The Running Intersection Relaxation of the Multilinear Polytope ⋮ Extension complexity of the correlation polytope ⋮ Worst-case analysis of clique MIPs ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side ⋮ New limits of treewidth-based tractability in optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List homomorphisms to reflexive graphs
• Treewidth. Computations and approximations
• Tree-width and the Sherali-Adams operator
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• On the power of unique 2-prover 1-round games
• The Linear Programming Polytope of Binary Constraint Problems with Bounded Tree-Width
• The Matching Polytope has Exponential Extension Complexity
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• How to Round Any CSP
• When is the evaluation of conjunctive queries tractable?
• The Polytope of Tree-Structured Binary Constraint Satisfaction Problems
• An inequality for the chromatic number of a graph
• Extended formulations in combinatorial optimization

This page was built for publication: Extended formulation for CSP that is compact for instances of bounded treewidth