On the Parameterized Complexity of Pooling Design
Authors:
- 1 November 2009
- journal article
- research article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 16 (11) , 1529-1537
Abstract
Pooling design is a very helpful tool for reducing the number of tests in DNA library screening, which is a key process to obtain high-quality DNA libraries for studying gene functions. Three basic problems in pooling design are, given an m × n binary matrix and a positive integer d, to decide whether the matrix is d-separable (d̄-separable, or d-disjunct). The three problems are all known to be coNP-complete. Since in most applications, d is a small integer compared to n, it is interesting to investigate whether there are efficient algorithms solving the above problems when the value of d is small. In this article, we give a negative answer to the above question by studying the parameterized complexity of these three problems, with d as the parameter. We show that the parameterized versions of all the three problems are co-W[2]-complete. An immediate implication of our results is that, given an m × n binary matrix and a positive integer d, a deterministic algorithm with running time f(d) × (mn)O(1) (where f is an arbitrary computable function) to decide whether the matrix is d-separable (d̄-separable, or d-disjunct) should not be expected.Keywords
This publication has 20 references indexed in Scilit:
- New Constructions of One- and Two-Stage Pooling DesignsJournal of Computational Biology, 2008
- Efficient Constructions of Disjunct Matrices with Applications to DNA Library ScreeningJournal of Computational Biology, 2007
- Improved Combinatorial Group Testing Algorithms for Real‐World Problem SizesSIAM Journal on Computing, 2007
- New Construction for Transversal DesignJournal of Computational Biology, 2006
- Optimal Two-Stage Algorithms for Group Testing ProblemsSIAM Journal on Computing, 2005
- Vertex Cover: Further Observations and Further ImprovementsJournal of Algorithms, 2001
- Maximally Efficient Two‐Stage ScreeningBiometrics, 2000
- New constructions of superimposed codesIEEE Transactions on Information Theory, 2000
- Some Completeness Results on Decision Trees and Group TestingSIAM Journal on Algebraic Discrete Methods, 1987
- The Detection of Defective Members of Large PopulationsThe Annals of Mathematical Statistics, 1943