Question

I am reading the introductory chapter in Parameterized Algorithms by Cygan et al. and I am having some problems with the distinction between complexity classes $\mathsf{W[1]}$ and $\mathsf{XP}$.

They explicitly define complexity class $\mathsf{XP}$ on p. 13 as the those problems that, given an instance $(x, k)$ of a parameterized problem, can be correctly decided by an algorithm in $O(f(k)\cdot|(x,k)|^{g(k)})$ time for functions $g, k$. I believe I understand this.

Complexity class $\mathsf{W[1]}$ is not explicitly defined. However, in the discussion of $k$-cliques on p. 9, they give an $O(n^k)$ algorithm for deciding whether a $k$-clique exists in a graph. As I understand it, therefore, the $k$-clique problem must be in $\mathsf{XP}$. However, the authors discuss it as a $\mathsf{W[1]}$ problem in a way that I find confusing.

My question, then, is twofold: (1) Am I right in thinking that $\mathsf{W[1]} \subseteq \mathsf{XP}$? I haven't been able to settle this by looking ahead in the book or by searching online. (2) Intuitively, what is the difference between the two classes? I have found defitions online, e.g. on Wikipedia, but not in language that I have found accessible. I would appreciate, therefore, if someone could provide more of an overview.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top