# What is a “slice” of a parameterized problem $(Q, \kappa)$?

In the book "Parameterized Complexity Theory" by J. Flum, and M. Grohe, there is a definition on page 7:

Definition 1.10.
Let $(Q, \kappa)$ be a parameterized problem and $\ell \in \mathbb{N}$. The $\ell$th slice of $(Q, \kappa)$ is the classical problem

$$(Q, \kappa)_\ell := \{x \in Q\ |\ \kappa(x) = \ell\}$$

Which is also referred to in the following chapters. Although I can understand the topics fairly enough, I still cannot understand the term "slice" in detail.

I kind of "memorized" that a slice of an fpt problem is solvable in PTIME. However, I do not really understand the logic behind it.

So, my question is:

What is a slice of a parameterized problem?

Consider the Graph Coloring problem.

Let $k$-Colorability be the language defined as follows.

• $\{(G, k)\ | \ \text{$G$is a$k$-colorable graph}\}$

Given $\ell \in \ \mathbb{N}$, the $\ell$-th slice of $(G, k)$ is the problem:

• $\{(G, k)_\ell | \ \text{$G$is a$k$-colorable graph and$k=\ell$}\}$

As you mention, a slice of an FPT problem is solvable in PTIME.
Using contraposition you get that if a slice is not solvable in PTIME than the problem is not FPT.
Indeed, if from one hand, 2-Coloring $\in \mathbb{P}$, on the other hand, 3-Coloring (or more generally, for any $k > 2$) $\notin \mathbb{P}$.
Hence, Colorability is not FPT.

The way you state it, a slice of an parameterized problem is the problem where we use some fixed constant for our problem parameter, instead of a 'free' variable. In a sense, we are only considering the subfamily of the problem for this particular constant, which is probably the logic behind the name 'slice'.

Indeed, if a problem $(Q,\kappa)$ is fixed parameter tractable, there is an algorithm that solves this problem with running time $O(f(n)\cdot g(\kappa))$, where $f$ is (sub)polynomial and $g$ can be superpolynomial. So, if we take a slice of this problem, then there is an algorithm that solves the problem '$(Q,l)$' ($=(Q,\kappa)_l$) in time $O(f(n)\cdot g(l)) = O(f(n))$, as $l$ and therefore $g(l)$ is constant. So $(Q,\kappa)_l$ is indeed solvable in PTIME.