Extended formulation for CSP that is compact for instances of bounded treewidth (Q907218)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Extended formulation for CSP that is compact for instances of bounded treewidth |
scientific article |
Statements
Extended formulation for CSP that is compact for instances of bounded treewidth (English)
0 references
25 January 2016
0 references
Summary: 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.
0 references
constraint satisfaction problems
0 references
linear programming
0 references
extended formulations
0 references
parameterized complexity
0 references
treewidth
0 references
