Parameterized study of the test cover problem

Robert Crowston*, Gregory Gutin, Mark Jones, Saket Saurabh, Anders Yeo

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


In this paper we carry out a systematic study of a natural covering problem, used for identification across several areas, in the realm of parameterized complexity. In the Test Cover problem we are given a set [n] = {1,...,n} of items together with a collection, , of distinct subsets of these items called tests. We assume that is a test cover, i.e., for each pair of items there is a test in containing exactly one of these items. The objective is to find a minimum size subcollection of , which is still a test cover. The generic parameterized version of Test Cover is denoted by -Test Cover. Here, we are given and a positive integer parameter k as input and the objective is to decide whether there is a test cover of size at most . We study four parameterizations for Test Cover and obtain the following: (a) k-Test Cover, and (n - k)-Test Cover are fixed-parameter tractable (FPT), i.e., these problems can be solved by algorithms of runtime , where f(k) is a function of k only. (b) -Test Cover and (logn + k)-Test Cover are W[1]-hard. Thus, it is unlikely that these problems are FPT.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2012 : 37th International Symposium, MFCS 2012, Proceedings
Volume7464 LNCS
Publication date2012
ISBN (Print)9783642325885
Publication statusPublished - 2012
Externally publishedYes
Event37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012 - Bratislava, Slovakia
Duration: 27. Aug 201231. Aug 2012


Conference37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7464 LNCS


Dive into the research topics of 'Parameterized study of the test cover problem'. Together they form a unique fingerprint.

Cite this