Why a feedback vertex set in tournaments induces an acyclic graph? A Feedback vertex set in a tournament, FVST, $T$ is a non-empty subset of its vertices like $W \subseteq V(T)$ such that $T[A]$ is acyclic where $A = V(T) \setminus W$.
On Page 84 (98 of PDF file), second paragraph from above, of the book "Parameterized Algorithms" (A free PDF by the authors at this link), it states both $T[W]$ and $T[A]$ are acyclic. By the definition of the FVST, it is clear that $T[A]$ is acyclic. However, it is not clear to me that $T[W]$ is acyclic, too. I've tried to come up with counter-examples, but couldn't. I've also tried to prove it, but cannot.
 A: This statement is based on the iterative compression technique.
Maybe you need to read Section 4.1 carefully.
In the disjoint version of FVST, we are given a tournament $T$, an integer $k$, and a feedback vertex set (FVS) $W$ of size $k + 1$, and we are asked whether there is an FVS $S$ of size at most $k$ disjoint from $W$.
In this problem, we need to find an FVS $S$ such that $S \cap W = \varnothing$. That is, every vertex in $W$ is not allowed to be put in the solution.
In this case, if $G[W]$ contains a cycle, we can directly return NO.

There are two main steps in the iterative compression technique.
For the example of the FVST problem.
There are three related problems:

*

*FVST

INPUT: A tournament $T$ and an integer $k$.
OUTPUT: Determine whether there exists an FVS $S$ of size at most $k$.

*

*Compression version of FVST (Compression-FVST)

INPUT: A tournament $T$, an integer $k$, and an FVS $U$ of size $k + 1$.
OUTPUT: Determine whether there exists an FVS $S$ of size at most $k$.

*

*Disjoint version of FVST (Disjoint-FVST)

INPUT: A tournament $T$, an integer $k$, and an FVS $W$ of size $k + 1$.
OUTPUT: Determine whether there exists an FVS $S$ of size at most $k$ disjoint from $W$.
Intuitively, the disjoint version is easier than the compression version, and the compression version is easier than the original version.
In the first step, we solve FVST by calling an algorithm for compression-FVST in linear time.
Specifically, we firstly order the vertices: $V(T) = \{ v_{1}, v_{2}, \ldots, v_{n} \}$, and define $V_{i} = \{ v_{1}, v_{2}, \ldots, v_{i} \}$.
Apperently, $T[V_{k}]$ has an FVS $S_{k}$ of size $k$, ($S_{k} = V_{k}$).
By the inductive method, suppose that $T[V_{i}] (k \leq i < n)$ has an FVS $S_{i}$ of size $k$.
Next, we consider $T[V_{i + 1}]$, one can easily find that $U_{i + 1} = S_{i} \cup \{v_{i + 1}\}$ is an FVS of $T[V_{i + 1}]$, and $|U_{i}| = k + 1$.
Now we call the algorithm for compression-FVST with the input $(T[V_{i + 1}], k, U_{i + 1})$, if it returns NO, then the original instance $(T, k)$ is also a NO-instance; otherwise, it returns an FVS $S_{i + 1}$ of $T[V_{i + 1}]$ of size at most $k$.
In the second step, we solve compression-FVST by calling the algorithm for disjoint-FVST. Specifically, we first enumerate the set $X = S \cap U$, there are $2^{k + 1}$ cases.
For each case, we can safely remove $X$ from the original graph.
In the remaining graph $T - X$, we let $W = U \setminus X$, and we know that every vertex in $W$ is undeletable.
Next, we call the algorithm for compression-FVST with the input $(T, k - |X|, W = U \setminus X)$. It is easy to see that $k - |X| = |W| - 1$.
Finally, according to the definition of the disjoint version, $W$ is not allowed to be put in the solution, which means that if $G[W]$ is not acyclic, then $(T, k - |X|, W = U \setminus X)$ is absolutely a NO-instance.
By the analysis of the running time on page 81, if the compression-FVST can be solved in time $c^{k}\cdot n^{\mathcal{O}(1)}$ for $c \geq 1$, then FVST can be solved in time $(c + 1)^{k}\cdot n^{\mathcal{O}(1)}$.
