Complexity Classes

$input \in \Sigma^* \times \N$

XP is a complexity class and $L \in XP$ iff there’s an algo that solves L:

• $T(A,input=x,parameter=k) \le |x|^{f(k)}$

FPT is a complexity class and $L \in FPT$ iff there’s an algo that solves L:

• $T(A,input=x,parameter=k) \le |x|^{O(1)} f(k)$

e.g. Vertex Cover/solusion size

• input: G=(V,E), integer k
• output: S=subset of V covering all edges, |S|≤k
• NP-complete if runtime only depends on $|\Sigma^*|$
• sol1: try all possible S
  • $O(n^km)$ → XP
• sol2: recursively pick a edge and decide deleting which vertex
  • branching: k is decreasing
  • $O(2^k(n+m))$ → FPT
• sol3: Kernelization
  • see below
  • $O(2^kk^2+n+m)$

e.g. feedback vertex set(FVS) of tournament/solusion size

• Tournament: a graph with a directed edge between each pair of vertices
• FVS(S): a subset of V such that G[V\S] is acyclic
• output: S, the FVS of a tournament graph with |S|≤k