Problem Definition 

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

kCardinality Tree Problem is NPhard. 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 EdgeWeighted KCardinality Tree Problem. 
Our approach 

We transform the kCardinality Tree Problem into a kCardinality Arborescence Problem
and solve it exactly using methods of integer linear programming. Our algorithm is implemented within a BranchandCut Framework, which uses a strong ILP model based on directed cuts. For a detailed information see our publication [1]. 
Our results 

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 stateoftheart metaheuristics in terms of the running time. 
Download 

Optimal solutions for all KCTLIB Instances computed by our algorithm. 
Contact 

maria.kandyba@cs.unidortmund.de 