# Elementary bounds on parameter in fixed-parameter tractability?

In the definition of (strong) fixed-parameter tractability, the time bound is an expression of the form $$f(k).p(|x|),$$ where the input instance is $(x,k)$ with parameter $k$, $p$ is a polynomial, and $f$ is a computable function.

It is possible to replace the computability requirement for $f$ with other classes of functions, as long as the notion of reduction is similarly restricted. (For instance, Flum and Grohe cover exponential and subexponential families in chapters 15–16 of their textbook, with the associated erf and serf reductions.)

Has anyone studied the family of elementary functions for the parameter bound $f$?

An elementary function can be bounded above by a fixed tower of exponentials, so this class is closed under composition. The growth in the parameter in a reduction must then be bounded above by an elementary function as well.

There do exist interesting problems from automata theory which are fixed-parameter tractable, but where the parameter bound is non-elementary (unless P = NP, see Frick and Grohe, doi: 10.1016/j.apal.2004.01.007). I am wondering if anyone has looked at the fixed-parameter tractable problems which exclude fixed values of the parameter leading to such "galactic" constants (to use Richard Lipton and Ken Regan's term). Speculating wildly, such a restriction might have useful connections with finite model theory, such as being characterized by a fragment of monadic second-order logic that doesn't lead to the non-elementary constants that can arise from applying Courcelle's Theorem to a fragment with unbounded quantifier alternation.

• What's an example of "interesting problems from automata theory which are fixed-parameter tractable, but where the parameter bound is non-elementary." Nov 17, 2011 at 16:30
• @SureshVenkat I believe it to be the model checking problem of FO and MSO formula on trees, parameterized by the length of formula. The lower bounds for FO and MSO are under some reasonable assumption in parameterized complexity and $NP\ne P$ respectively. Nov 18, 2011 at 6:55

• I'm not exactly sure what you have in mind. For the general framework, he considers arbitrary classes of "growth"-functions. For example, reductions are defined for arbitrary "growth"-classes of functions (Section 3.4, p.22). The classes $\mathcal E_t$, $\mathcal{QE}_t$ and $\mathcal{PE}_t$ (defined on page 19 and 20) are those functions that can be bounded by a tower of exponentials of height $t$. (These three differ by what you have within the $exp^t(\cdot)$.) Is this what you mean with elementary parameter bound? These classes are then used a lot, and have a crucial role in Chapter 6. Nov 19, 2011 at 18:11