Box-total dual integrality and edge-connectivity in series-parallel graphs

29th of April 2022, at 15:00

Room: Online via Teams

https://teams.microsoft.com/l/meetup-join/19%3adacd63e97f9e48e896f537ace22a27bf%40thread.tacv2/1650924282850?context=%7b%22Tid%22%3a%2281e7c4de-26c9-4531-b076-b70e2d75966e%22%2c%22Oid%22%3a%22c00d08df-c86f-4f81-a9c8-6287a3bb947d%22%7d

Speaker: Emiliano Lancini

Title: Box-total dual integrality and edge-connectivity in series-parallel graphs

Abstract:

A rational system of linear inequalities is totally dual integral (TDI) if, for all integer cost vectors, the dual problem is either unfeasible or it has an integer optimal solution. We are interested in the stronger property of box-TDIness : a system is box-TDI if it is TDI under the addition of any rational box constraint. A polyhedron that can be described by a box-TDI system is called a box-TDI polyhedron.

In this work we show  that the k-edge-connected spanning subgraph polyhedron of a graph G---namely, the convex hull of all k-edge-connected spanning subgraphs of G---is box-TDI if and only if G is series-parallel.  Moreover, we provide a TDI system with integer coefficients describing this polyhedron when G is series-parallel.

keywords : series-parallel graph, box-total dual integrality, edge-connectivity