Relationship between complexity classes XP and W[1]?

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.

Answer 1

1) Yes, you are right: W[1] is a subset of XP. As you noticed, $k$-clique is in XP. The class W[1] is (usually by definition) the closure of that problem under FPT-reductions. XP is closed under these reductions. Hence the subsetship.

2) Citing another answer of mine, here is a bit of intuition about XP:

The practical importance of XP is as a door to parameterized complexity analysis. Once a problem is recognized as belonging to XP it makes sense to investigate its exact parameterized complexity. If it does not even belong to XP, parameterized analysis doesn't make much sense. It can also be argued that in that case the parameterization is not meaningful.

In that sense, XP is the hardest intractable class of parameterized complexity theory. In an even fuzzier sense, on the very opposite side of the spectrum, W[1] is the easiest parameterized version of NP.

Gaining an intuition for W[1] is not exactly made easy (in the past I tried in this answer). As said, it is usually defined by completeness of a problem (like $k$-clique). Definitions using machine models exist (e.g. Chen, Flum, Grohe: Machine-based methods in parameterized complexity theory. TCS 339(2-3), 2005). But that does not imply they are suitable for entry-level understanding of the class. I suggest you just take W[1] as the sum of the facts you know about it.