## 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.*