The \(k\)-feature set problem is \(W[2]\)-complete

DOI10.1016/S0022-0000(03)00081-3zbMath1114.68426MaRDI QIDQ1877698

Carlos Cotta, Pablo Moscato

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

A parameterized perspective on packing paths of length two ⋮ Stochastic local search for the FEATURE SET problem, with applications to microarray data ⋮ Exploiting hidden structure in selecting dimensions that distinguish vectors ⋮ Separating sets of strings by finding matching patterns is almost always hard ⋮ The complexity of dependency detection and discovery in relational databases ⋮ Tight lower bounds for certain parameterized NP-hard problems

Cites Work

• A Gentle Introduction to Memetic Algorithms
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Unnamed Item

This page was built for publication: The \(k\)-feature set problem is \(W[2]\)-complete