Efficient exact algorithm for the k-Cardinality Tree Problem

M. Chimani, M. Kandyba, I. Ljubic, P. Mutzel
May 20, 2008

Problem Definition

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

About the problem

  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.

Our approach

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


  Optimal solutions for all KCTLIB Instances computed by our algorithm.



[1] M. Chimani, M. Kandyba, I. Ljubic, P. Mutzel. Obtaining Optimal k-Cardinality Trees Fast. Proceedings of Workshop on Algorithm Engineering & Experiments 2008, San Francisco (ALENEX'08).