### M. Cesati, M. Fellows, ``Sparse Parameterized Problems'',
Annals of Pure and Applied Logic 82 (1996) 1-15, Elsevier

Sparse languages play an important role in classical
structural complexity theory. In this paper we introduce a
natural definition of *sparse* problems for
parameterized complexity theory. We prove an analog of
Mahaney's theorem: there is no sparse parameterized problem
which is hard for the t-th level of the W hierarchy, unless the
W hierarchy itself collapses up to level t. The main result is
proved for the most general form of parametric many:1
reducibility, where the parameter functions are not assumed to
be recursive. This provides one of the few instances in
parameterized complexity theory of a full analog of a major
classical theorem. The proof involves not only the standard
technique of left sets, but also substantial circuit
combinatorics to deal with the problem of small weft, and a
diagonalization to cope with potentially nonrecursive parameter
functions. The latter techniques are potentially of interest
for further explorations of parameterized complexity analogs of
classical structural results.

Back to the Marco
Cesati's research page.