The box-TDI system associated with 2-edge connected spanning subgraphs
Let G G be a graph and let A A be its cutset-edge incidence matrix. We prove that the linear system 1 2 A x ? 1 , x ? 0 is box totally dual integral (box-TDI) if and only if G G is a series-parallel graph; a by-product of this characterization is a structural description of a box-TDI system on matroids. Our results strengthen two previous theorems obtained respectively by Cornujols, Fonlupt, and Naddef and by Mahjoub which assert that both polyhedra { x ? 1 2 A x ? 1 , x ? 0 } and { x ? 1 2 A x ? 1 , 1 ? x ? 0 } are integral if G G is series-parallel.
graph box total dual integrality polyhedron cut traveling salesman problem