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

<p>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.</p>

CC BY-SA 3.0
2017-07-14T22:24:44.300Z
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.
daniello
CC BY-SA 3.0
2017-07-16T08:05:04.277Z
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.
Michael Wehar
CC BY-SA 3.0
2017-07-16T08:06:04.247Z
I've seen two notions of linear fpt-reduction in the literature that require $g(k)$ to be bounded.
Michael Wehar
CC BY-SA 3.0
2017-07-13T09:44:14.223Z
2017-07-16T08:51:09.310Z
2017-07-16T08:51:09.310Z
Ronald de Haan
<p>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 &amp; Fellows 2013 textbook.</p>

<p>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 &amp; Fellows does not mention anything about the structure of $\mathsf{XP}$ beyond Proposition 27.1.1, and the discussion in the Flum &amp; Grohe 2006 textbook isn't much more detailed.</p>

<p>Following on from my earlier question <a href="https://cstheory.stackexchange.com/q/38283">Limits of variants of Independent Set?</a> 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?</p>

<p>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}$.</p>

CC BY-SA 3.0
2017-05-26T04:51:30.327Z
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)}$.
Michael Wehar
<cc.complexity-theory><reference-request><parameterized-complexity>
Name for "uniformly polynomial" subclass of XP?
András Salamon
# Name for "uniformly polynomial" subclass of XP?

(Asked by: username_0 on 2017-05-25)

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?](https://cstheory.stackexchange.com/q/38283) 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}$.

**Tags:** cc.complexity-theory, reference-request, parameterized-complexity

> **Comments:**
> **username_1**: 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)}$.  

---

## 1 answers

### Answer by username_2 on 2017-07-13. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_3**: 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.  
> **username_1**: 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.  
> **username_1**: I've seen two notions of linear fpt-reduction in the literature that require $g(k)$ to be bounded.  

---

