On the Parameterized Complexity of Pooling Design

Abstract

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.