2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
0

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.