K-Cardinality Subgraphs

The problem of finding a connected subgraph S of a given graph G = (V,E) containing exactly k edges which is minimal with respect to edge weights w(e) ∈ ℝ is considered. After stating that the problem is NP-hard an integer programming formulation will be given. Some classes of inequalities are shown to be facet-defining for the corresponding polytope. An algorithm for the separation problem for the most important class of inequalities is given which has been implemented in a branch-and-cut approach. Finally the results of this algorithm are compared with a heuristic based on Prim’s algorithm.