The k-FEATURE SET Problem is W[2]-Complete

C. Cotta, P. Moscato

Journal of Computer and System Sciences 67(4):686-690, 2003

© Elsevier Science 2003. All rights reserved.


We prove the W[2]-completeness of the feature subset selection problem when the cardinality of the subset is the parameter. Aside from the many applications the problem has in the data mining literature, the problem is highly relevant in Computational Biology since it arises in differential gene expression analysis using microarray technologies. It is also related to genetic-based prognosis and regulatory interaction discovery using DNA chip technologies.

Download BibTEX entry
Electronic version available from ScienceDirect
Download PDF version (146K) - preprint
[Back to publications page].