A parameterized complexity analysis of combinatorial feature selection problems

Vincent Froese, René Van Bevern, Rolf Niedermeier, Manuel Sorge

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings
Pages445-456
Number of pages12
DOIs
Publication statusPublished - 15 Oct 2013
Externally publishedYes
Event38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 - Klosterneuburg, Austria
Duration: 26 Aug 201330 Aug 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8087 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013
CountryAustria
CityKlosterneuburg
Period26.08.201330.08.2013

Fingerprint Dive into the research topics of 'A parameterized complexity analysis of combinatorial feature selection problems'. Together they form a unique fingerprint.

Cite this