On the minimum-cost λ-edge-connected k-subgraph problem

摘要

In this paper, we propose several integer programming (IP) formulations to exactly solve the minimum-cost λ-edge-connected k-subgraph problem, or the (k, λ)-subgraph problem, based on its graph properties. Special cases of this problem include the well-known k-minimum spanning tree problem (if λ=1), λ-edge-connected spanning subgraph problem (if k= |V|) and k-clique problem (if λ = k - 1 and there are exact k vertices in the subgraph). As a generalization of k-minimum spanning tree and a case of the (k, λ)-subgraph problem, the (k, 2)-subgraph problem is studied, and some special graph properties are proved to find stronger and more compact IP formulations. Additionally, we study the valid inequalities for these IP formulations. Numerical experiments are performed to compare proposed IP formulations and inequalities.