10
$\begingroup$

Suppose $L$ is a parameterized language with respect to some alphabet $\Sigma$. The $k$-slice of $L$ is $L_k = L \cap \{(x,k) \mid x \in \Sigma^{*}\}$, the set of instances in $L$ which have parameter $k$. The complexity class $\mathsf{XP}$ contains the parameterized languages $L$ such that $L_k \in P$ for each $k$, possibly with a different algorithm and polynomial running time bound for each $k$. Each fixed-parameter tractable language is in $\mathsf{XP}$, and there are languages in $\mathsf{XP}$ that are not in $\mathsf{FPT}$; this is Proposition 27.1.1 in the Downey & Fellows 2013 textbook.

However, $\mathsf{XP}$ seems to have nontrivial structure beyond this, since one can stratify this class based on how fast the degree of the bounding polynomial grows with $k$: for $\mathsf{FPT}$ the degree is constant, whereas for $\mathsf{XP}$ it can grow arbitrarily. Downey & Fellows does not mention anything about the structure of $\mathsf{XP}$ beyond Proposition 27.1.1, and the discussion in the Flum & Grohe 2006 textbook isn't much more detailed.

Following on from my earlier question Limits of variants of Independent Set? is there a name for the subclass $\mathsf{Q}$ of $\mathsf{XP}$ where $L \in \mathsf{Q}$ if there is a polynomial $g_L$ such that every instance $(x,k)$ in $L$ can be decided in at most $|x|^{g_L(k)}$ steps?

In other words, this class $\mathsf{Q}$ allows only up to $|x|^{\text{poly}(k)}$ time instead of $|x|^{g(k)}$ time for some arbitrary function $g$ as for $\mathsf{XP}$.

$\endgroup$
  • $\begingroup$ This is a great question! I'm actually very interested in the subclass where the polynomial is linear. That is, Q allows only up to $\vert x \vert ^{O(k)}$. $\endgroup$ – Michael Wehar May 26 '17 at 4:51
6
$\begingroup$

I don't think this subclass of $\textsf{XP}$ has been studied in the literature (and given a name).

One reason why researchers might shy away from studying this subclass, is that it is not closed under fpt-reductions (and so one would have to deal with an 'annoying' new type of reductions). This is because fpt-reductions allow the parameter value to blow up superpolynomially (as long as it is bounded by some computable function of the old parameter value). To get a restricted notion of fpt-reductions under which your subclass of $\textsf{XP}$ is closed, you would need to add the restriction that fpt-reductions require the new parameter value to be bounded by some polynomial of the old parameter value.

$\endgroup$
  • 1
    $\begingroup$ The reductions you talk about have been studied in the context of kernlizaiton under the name "polynomial parameter transformations", however these have to run in polynomial time. $\endgroup$ – daniello Jul 14 '17 at 22:24
  • $\begingroup$ I subjectively think that a new type of reduction could be good (not very annoying). I've always been skeptical of fpt-reductions allowing for $g(k)$ to be unbounded. $\endgroup$ – Michael Wehar Jul 16 '17 at 8:05
  • $\begingroup$ I've seen two notions of linear fpt-reduction in the literature that require $g(k)$ to be bounded. $\endgroup$ – Michael Wehar Jul 16 '17 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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