ALCOMFT-TR-02-80

K.M.J. De Bontridder, B.V. Halld\'orsson, M.M. Halld\'orsson, J.K. Lenstra, R. Ravi and l. Stougie
Approximation algorithms for the minimum test set problem
Utrecht. Work package 3. May 2002.

Abstract: In the minimum test set problem a set of items is given together with a collection of subsets of the items, called tests. A smallest set of tests is to be selected such that for every pair of items there is a test in the selection that contains exactly one of the two items. This problem is known to be NP-hard in general. We show that, unless P=NP, no algorithm can have an essentially better worst-case performance ratio than the greedy algorithm. In the special case where each test contains at most k items, we devise an O(log k)-approximation algorithm.

Special attention is paid to the case in which each test contains only one or two items. A strong relation with a packing problem on a graph is established, showing immediately that also this special minimum test set problem is NP-hard, contradicting a claim in [Garey & Johnson 1979, page 222]. Furthermore we show APX-hardness of both problems. We derive performance guarantees for a series of local improvement heuristics.

The latter belong to the scarce results on performance guarantees of local search algorithms in the literature.

Postscript file: ALCOMFT-TR-02-80.ps.gz (138 kb).