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.


Abstract

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
[Back to publications page].