Tree-width and the Sherali–Adams operator

We describe a connection between the tree-width of graphs and the Sherali–Adams reformulation procedure for 0/1 integer programs. For the case of vertex packing problems, our main result can be restated as follows: let G be a graph, let k⩾1 and let &xcrcmflx; ∈ R^V(G) be a feasible vector for the formulation produced by applying the level-k Sherali–Adams algorithm to the edge formulation for STAB(G). Then for any subgraph H of G, of tree-width at most k, the restriction of ◯ to R^V(H) is a convex combination of stable sets of H.