Given an undirected graph $G=(V,E)$ with edge weights and a positive integer number $k$, the $k$-Cardinality Tree (KCT) problem consists of finding a subtree $T$ of $G$ with exactly $k$ edges and the minimum possible weight.

The $k$-Cardinality Tree Problem is NP-hard. Both exact and heuristic methods have been developed in the past. A detailed information about the problem, a literature overview and a collection of benchmark instance sets is presented at KCTLIB - A Library for the Edge-Weighted K-Cardinality Tree Problem.

We transform the $k$-Cardinality Tree Problem into a $k$-Cardinality Arborescence Problem and solve it exactly using methods of integer linear programming. Our algorithm is implemented within a Branch-and-Cut Framework, which uses a strong ILP model based on directed cuts. For a detailed information see our publications listed below (in ascending order of depth).

Our approach is the first exact algorithm which is able to solve all benchmark instances of KCTLIB to provable optimality within reasonable time bounds. For instances with 1000 nodes or less it even outperformed the state-of-the-art metaheuristics in terms of the running time.

Download the optimal solutions for all KCTLIB instances computed by our algorithm: optsol_tar.gz

• M. Chimani, M. Kandyba, I. Ljubic, P. Mutzel. Obtaining Optimal k-Cardinality Trees Fast. 10th Workshop on Algorithm Engineering & Experiments 2008, San Francisco (ALENEX08), SIAM, pp. 27-36. (link to original)

• M. Chimani, M. Kandyba, I. Ljubic, P. Mutzel. Obtaining Optimal k-Cardinality Trees Fast. ACM Journal of Experimental Algorithmics, Vol. 14(2), pp. 5.1-5.23, 2009.

• M. Kandyba. Exact Algorithms for Network Design Problems using Graph Orientations. PhD thesis, TU Dortmund, 2011. (handle)