8 citations · 9 across the 3 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.DS2015★ 8 cited
Extension Complexity, MSO Logic, and Treewidth
Petr Kolman, Martin Koutecký, Hans Raj Tiwary
We consider the convex hull of all satisfying assignments of a given MSO formula on a given graph . We show that there exists an extended formulation of the polytop…
cs.CC2015
Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth
Petr Kolman, Martin Koutecký
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 bo…