Extended formulation for CSP that is compact for instances of bounded treewidth (Q907218): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: Publication / rank | |||
Normal rank | |||
Revision as of 01:35, 5 March 2024
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
