The k-node connected subgraph problem: Polyhedral analysis and Branch-and-Cut

In this paper we consider the k-node connected subgraph problem. We propose an integer linear programming formulation for the problem and investigate the associated polytope. We introduce further classes of valid inequalities and discuss their facial aspect. We also devise separation routines and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using those results, we devise a Branch-and-Cut algorithm and present some preliminary computational results.