Parameterized study of the test cover problem

DOI10.1007/978-3-642-32589-2_27MaRDI QIDQ2912727zbMATH OpenOpenAlexFDO

Authors Robert Crowston, G. Gutin, Mark P. Jones, Saket Saurabh, A. Yeo

Publication date 25 September 2012

Published in Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.0117

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 {sc Test Cover} problem we are given a set $[n]=1,\mathrm{...},n$ of items together with a collection, $calT$, of distinct subsets of these items called tests. We assume that $calT$ is a test cover, i.e., for each pair of items there is a test in $calT$ containing exactly one of these items. The objective is to find a minimum size subcollection of $calT$, which is still a test cover. The generic parameterized version of {sc Test Cover} is denoted by $p(k,n,|calT|)$-{sc Test Cover}. Here, we are given $([n],calT)$ and a positive integer parameter $k$ as input and the objective is to decide whether there is a test cover of size at most $p(k,n,|calT|)$. We study four parameterizations for {sc Test Cover} and obtain the following: (a) $k$-{sc Test Cover}, and $(n-k)$-{sc Test Cover} are fixed-parameter tractable (FPT). (b) $(|calT|-k)$-{sc Test Cover} and $(logn+k)$-{sc Test Cover} are W[1]-hard. Thus, it is unlikely that these problems are FPT.

Recommendations

• Parameterizations of test cover with bounded test sizes
• (Non-)existence of polynomial kernels for the test cover problem
• Approximation algorithms for the test cover problem
• Partially Polynomial Kernels for Set Cover and Test Cover
• scientific article; zbMATH DE number 1947395

Cited in

(20)

• Approximation algorithms for the test cover problem
• Induced-bisecting families of bicolorings for hypergraphs
• (Non-)existence of polynomial kernels for the test cover problem
• The generalized test collection problem
• System of unbiased representatives for a collection of bicolorings
• Fixed-parameter tractable algorithms for tracking shortest paths
• Alternative parameterizations of \textsc{Metric Dimension}
• Combinatorial search in two and more rounds
• Parameterizations of test cover with bounded test sizes
• Test sets for vertex cover problems
• Randomized adaptive test cover
• Parameterized testability
• Deterministic versus randomized adaptive test cover
• A faster branch-and-bound algorithm for the test-cover problem based on set-covering techniques
• scientific article; zbMATH DE number 1947395 (Why is no real title available?)
• Parameterized testability
• Experimental and Efficient Algorithms
• Partially polynomial kernels for set cover and test cover
• Structural parameterization of locating-dominating set and test cover
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover

This page was built for publication: Parameterized study of the test cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912727)