Extended formulation for CSP that is compact for instances of bounded treewidth (Q907218)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6534961
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Extended formulation for CSP that is compact for instances of bounded treewidth |
scientific article; zbMATH DE number 6534961 |
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
0.7898144125938416
0 references
0.7881690859794617
0 references
0.7875563502311707
0 references
0.7699146866798401
0 references
0.7579492926597595
0 references
