Theoretical Computer Science / Theoretische Informatik

Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]

User Tools


Efficient exact algorithm for the k-Cardinality Tree Problem

About the problem

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.

Our approach and results

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

Publications

research/kct.txt · Last modified: April 17, 2013 (21:19) by chimani