13
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ What's an example of "interesting problems from automata theory which are fixed-parameter tractable, but where the parameter bound is non-elementary." $\endgroup$
    – Suresh Venkat
    Nov 17, 2011 at 16:30
  • 2
    $\begingroup$ @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. $\endgroup$
    – Regularity
    Nov 18, 2011 at 6:55

1 Answer 1

Reset to default
13
$\begingroup$

In his dissertation thesis "Modifizierte parametrische Komplexitatstheorie", Mark Weyer considered, among other things, hierarchies within FPT w.r.t. the function f and reductions between them. He also did indeed relate these sub-hierarchies to fragments of FO and MSO: Chapter 6 is essentially about the relation between FO/MSO (the number of quantifier alternations of the formulas) and the function f(w) in Courcelle's theorem (w being the treewidth). He considered both upper and lower bounds and, using the aforementioned reduction framework between certain hierarchies within FPT, he was able to give quite tight bounds. The examiners of the thesis were Flum and Grohe.

Unfortunately the thesis is in German, and I'm not aware whether material of his thesis has been published in an English journal. I'm therefore aware that they might be of limited use for you, but nevertheless the references therein might be a good starting point.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks, had not thought to check theses. This looks highly relevant to the applications I mentioned. I am probably missing something, but other than a brief mention on page 69, elementary parameter bounds do not seem to be of interest to Weyer. $\endgroup$
    – András Salamon
    Nov 19, 2011 at 16:59
  • 2
    $\begingroup$ 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. $\endgroup$
    – Alexander Langer
    Nov 19, 2011 at 18:11
  • 1
    $\begingroup$ For elementary bounds, it is enough to just consider the union of all the exponential functions. This is mentioned by Weyer on page 69 of his thesis, but the issue does not seem to be dealt with any further. $\endgroup$
    – András Salamon
    Nov 19, 2011 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.