Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth

  • Petr Kolman
  • Martin Koutecký
DOI: https://doi.org/10.37236/5474
Keywords: Constraint satisfaction problems, Linear programming, Extended formulations, Parameterized complexity, Treewidth

Abstract

In this paper we provide an extended formulation for the class of constraint satisfaction problems and prove that its size is polynomial for instances whose constraint graph has bounded treewidth. This implies new upper bounds on extension complexity of several important NP-hard problems on graphs of bounded treewidth.
Published
2015-11-27
Issue
Volume 22, Issue 4 (2015)
Article Number
P4.30