LAUSR

Connectivity is a central concept in combinatorial optimization, graph theory, and operations research. In many applications, one is interested in finding an optimal subset of vertices with the essential requirement that the vertices are connected, but not how they are connected. In other words, it is not relevant which edges are selected to obtain connectivity. This article is concerned with the exact solution of such problems via integer programming. We analyze and compare (mixed) integer programming formulations with respect to the strength of their linear programming relaxations. Along the way, we also provide a tighter (compact) description of the connected subgraph polytope—the convex hull of subsets of vertices that induce a connected subgraph. Furthermore, we give a (compact) complete description of the connected subgraph polytope for graphs with no four independent vertices.