Spring til hovednavigation Spring til søgning Spring til hovedindhold

Parameterized study of the test cover problem

  • Robert Crowston*
  • , Gregory Gutin
  • , Mark Jones
  • , Saket Saurabh
  • , Anders Yeo
  • *Corresponding author af dette arbejde
  • Royal Holloway, University of London
  • Institute of Mathematical Sciences India
  • University of Johannesburg

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

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.

OriginalsprogEngelsk
TitelMathematical Foundations of Computer Science 2012 : 37th International Symposium, MFCS 2012, Proceedings
Vol/bind7464 LNCS
Publikationsdato2012
Sider283-295
ISBN (Trykt)9783642325885
DOI
StatusUdgivet - 2012
Udgivet eksterntJa
Begivenhed37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012 - Bratislava, Slovakiet
Varighed: 27. aug. 2012 → 31. aug. 2012

Konference

Konference37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012
Land/OmrådeSlovakiet
ByBratislava
Periode27/08/2012 → 31/08/2012
NavnTheoretical Computer Science and General Issues
Vol/bind7464

Fingeraftryk

Dyk ned i forskningsemnerne om 'Parameterized study of the test cover problem'. Sammen danner de et unikt fingeraftryk.

Citationsformater