Box-total dual integrality and edge-connectivity

• 成果类型: Article
• 署名作者: Barbato, Michele; Grappe, Roland; Lacroix, Mathieu; Lancini, Emiliano
• 署名单位: University of Milan; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01743-x
• 发表日期: 2023
• 页码: 307-336
• 关键词: spanning subgraph; polyhedra; DESIGN

摘要

Given a graph G = (V, E) and an integer k >= 1, the graph H = (V, F), where F is a family of elements (with repetitions allowed) of E, is a k-edge-connected spanning subgraph of G if H cannot be disconnected by deleting any k - 1 elements of F. The convex hull of incidence vectors of the k-edge-connected subgraphs of a graph G forms the k-edge-connected subgraph polyhedron of G. We prove that this polyhedron is box-totally dual integral if and only if G is series-parallel. In this case, we also provide an integer box-totally dual integral system describing this polyhedron.