Vincent Froese, RenĂ© van Bevern, Rolf Niedermeier, and Manuel Sorge. A parameterized complexity analysis of combinatorial feature selection problems. In Proceedings of the 38th International on Symposium Mathematical Foundations of Computer Science (MFCS'13), Klosterneuburg, Austria, volume 8087 of Lecture Notes in Computer Science, pages 445–456. Springer, 2013. The final version of this article appeared in Journal of Computer and System Sciences.

We examine the algorithmic tractability of NP-hard combinatorial feature selection problems in terms of parameterized complexity theory. In combinatorial feature selection, one seeks to discard dimensions from high-dimensional data such that the resulting instances fulfill a desired property. In parameterized complexity analysis, one seeks to identify relevant problem-specific quantities and tries to determine their influence on the computational complexity of the considered problem. In this paper, for various combinatorial feature selection problems, we identify parameterizations and reveal to what extent these govern computational complexity. We provide tractability as well as intractability results; for example, we show that the Distinct Vectors problem on binary points is polynomial-time solvable if each pair of points differs in at most three dimensions, whereas it is NP-hard otherwise.

bib | DOI | journal version ] Back

This file was generated by bibtex2html 1.98.