## 5 Experimental Results
### Comparison of NewKLS_FVS with Other Algorithms  
In order to verify the efficiency and performance of the proposed algorithm, the performance of the proposed heuristic for the feedback vertex set problem is also compared to that of several others. Note that the proposed problem can be solved approximately by various heuristics, including simulated annealing (SA) and variable neighborhood search (VNS). * **Simulated annealing:** The simulated annealing algorithm was introduced to solve combinatorial optimization problems proposed by [PERSON] [25]. Since then, it has been widely investigated to solve many combinatorial optimization problems. Simulated annealing allows a transition to go opposite towards achieving the goal with a probability. As a result, the simulated annealing algorithm has some opportunities to jump out of the local minima. As preparation, for a given graph, \(G\), and a positive integer, \(k\), a partition \((S_{1},S_{2})\) of \(V(G)\) is found, such that \(G[S_{1}]\) is acyclic. Then, the parameters, \(T_{0}\) (initial temperature), \(T_{s}\) (stop temperature) and \(\alpha\) (cooling down coefficient), are required as input. For convenience, the edge numbers of \(G[S_{1}]\) and \(G[S^{\prime}_{1}]\) are denoted by \(e(S_{1})\) and \(e(S^{\prime}_{1})\), respectively. After the preparation, the algorithm begins with a randomly generated partition \((S_{1},S_{2})\) of \(V(G)\). Then, a partition \((S^{\prime}_{1},S^{\prime}_{2})\) is chosen that is obtained by swapping two elements from \(S_{1}\) and \(S_{2}\). If \(e(S^{\prime}_{1})\) is fewer than \(e(S_{1})\), then \((S^{\prime}_{1},S^{\prime}_{2})\) is accepted. Otherwise, it is accepted according to the simulated annealing rule. At the end of each iteration, the temperature would cool down. Usually, let \(T=\alpha T\), where \(\alpha\in(0,1)\). If \(G[S_{1}]\) is acyclic, the procedure terminates successfully, and an acyclic induced subgraph with order \(k\) would be returned. When the temperature reaches \(T_{s}\), the procedure also terminates. The pseudocode is presented in Algorithm 3, where \(u(0,1)\) denotes a random number in \((0,1)\). \begin{table}
\begin{tabular}{l l l l l} \hline
**Instance** & \(\mathbf{L}\) & **Best** & **Worst** & **Average** \\ \hline G(800,0.5) & 100 & 17 & 13 & 14 \\  & 200 & 15 & 13 & 14 \\  & 300 & 16 & 13 & 14 \\  & 400 & 17 & 13 & 14 \\  & 500 & 16 & 13 & 14 \\  & 600 & 16 & 14 & 15 \\  & 700 & 17 & 13 & 15 \\  & 800 & 16 & 15 & 15 \\  & 900 & 18 & 13 & 15 \\  & 1,000 & 17 & 14 & 15 \\ \hline \end{tabular}
\end{table} 
Table 2: _Cont._* **Variable neighborhood search:**[PERSON] and [PERSON]\(\acute{c}\)[10, 11, 12] introduced the variable neighborhood search (VNS) method in combinatorial problems. In [5], it was applied to solve the maximum clique problem. It constructs different neighborhood structures, which are used to perform a systematic search. The main idea of variable neighborhood search is that when it does not find a better solution for a fixed number of iterations, the algorithm continues to search in another neighborhood until a better solution is found. Denote \(\mathcal{N}_{k}\), \((k=1,2,\cdots\), \(k_{max})\) as a finite set of pre-selected neighborhood structures and \(\mathcal{N}_{k}(X)\) as the set of solutions in the \(kth\) neighborhood of \(X\). The steps of the basic VNS are presented in Algorithm 4 (see [5]). To solve the feedback vertex set problem, the neighborhood structure is described as follows. Let \((S_{1},S_{2})\) be the current partition, for a positive integer, \(k\), with \(k<\min\{|S_{1}|,|S_{2}|\}\); define \(B_{k}(S)\) as the set of the \(k\)-subset of \(S\). The \(kth\) neighborhood of \(P\) is defined by: \[\mathcal{N}_{k}(S_{1},S_{2})=\{(S_{1}\cup U_{2}\setminus U_{1},S_{2}\cup U_{1 }\setminus U_{2})|U_{1}\in B_{k}(V_{r}),U_{2}\in B_{k}(V_{b})\}\] (1) The proposed algorithms operate the partition, \(S_{1},S_{2}\).