Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth
classification
💻 cs.CC
keywords
boundedtreewidthconstraintextendedformulationinstancesproblemsbounds
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.