## 3 KLS-Based Local Search Algorithm  
In the simple local search procedure, the current solution is changed by adding or removing one vertex. The idea of KLS-based local search is to operate more vertices for each time. That is to say, the current solution is changed by way of adding or removing more than one vertex. Furthermore, the number of operated vertices is not limited in KLS. Therefore, it is a variable depth local search, also called \(k\)-opt local search.  
As a comparison, the KLS-based local search is explored to solve the feedback vertex set problem. Then, a variable depth-based local search with a randomized scheme is proposed to solve this problem. For a given graph, \(G\), it can be observed that if \(S\) is acyclic, then \(V(G)\setminus S\) is a feedback vertex set. Therefore, such a vertex set, \(S\), with maximum cardinality corresponds to a feedback vertex set with minimum cardinality. Hence, the goal is to find a vertex set, \(S\in V(G)\), with maximum cardinality, for which \(G[S]\) is acyclic. The main framework of this algorithm is taken from \(KLS\) in [4].  
The following notations will be used to describe the algorithms.  
\(\bullet\)\(CF\): the current vertex subset, \(CF\), for which \(G[CF]\) is acyclic.  
\(\bullet\)\(PA\): the possible vertex set of addition. _i.e._, \(PA=\{v|\text{the subgraph induced by }CF\cup\{v\}\text{ is acyclic}\}\)  
\(\bullet\)\(f(v)\):the degree of \(v\) in the graph, \(G[CF]\);  
\(\bullet\)\(f^{+}(v)\): the degree of \(v\) in the graph, \(G[CF\cup\{v\}]\), _i.e._, \(f^{+}(v)=d_{G[CF\cup\{v\}]}(v)\).  
First, a vertex set, \(CF\subseteq V\), is randomly generated as an initial acyclic vertex set. If \(CF\) is not maximal, then a vertex, \(v\in PA\), that minimizes \(f(v)\) is chosen to add to \(CF\). On the contrary, if \(CF\) is maximal, then a vertex, \(v\in CF\), with the maximum degree is chosen to be dropped. In the search process, some vertices are iteratively added or removed, ensuring that the vertex set, \(CF\), is acyclic at each iteration. In order to avoid cycling, when a vertex, \(v\), is added (resp.dropped), \(v\) would not be dropped (resp.added) immediately. The pseudocode of the procedure is shown in Algorithm 1 (\(k\)-opt-LS).  
```
1:\(G\): a graph with the vertex set, \(\{1,2,\cdots,n\}\);
2:\(CF\): the current acyclic vertex set;
3:\(PA\): the possible vertex set of addition;
4: generate an acyclic vertex set, \(CF\), randomly.
5:repeat
6:\(CF_{Prev}\gets CF\); \(D\gets CF_{Prev}\); \(P\leftarrow\{1,2,\cdots,n\}\); \(g\gets 0\); \(g_{max}\gets 0\)
7:repeat
8:if\(PA\cap P\
eq\emptyset\)then
9: find a vertex, \(v\), from \(PA\cap P\) that minimizes \(f^{+}(v)\). if multiple vertices are found, select one randomly.
10:\(CF\gets CF\cup\{v\}\); \(g\gets g+1\); \(P\gets P\setminus\{v\}\);
11:else
12:if\(CF\cap P\
eq\emptyset\)then
13: find a vertex, \(v\), from \(CF\cap P\) that maximizes \(f(v)\). if multiple vertices are found, select one randomly.
14:\(CF\gets CF\setminus\{v\}\); \(g\gets g-1\); \(P\gets P\setminus\{v\}\);
15:if\(v\) is contained in \(CF_{Prev}\)then
16:\(D\gets D\setminus\{v\}\);
17:endif
18:endif
19:endif
20:endif
21:until\(D=\emptyset\)
22:until\(g_{max}\leq 0\)
```  
**Algorithm 1**\(k\)-opt-LS(\(G,CF,PA\))  
In this local search algorithm, if \(PA=\emptyset\), then the acyclic vertex set, \(CF\), is maximal. In this case, a vertex, \(v\in CF\), will be dropped; otherwise, a vertex \(v\in V\setminus CF\) will be added. Algorithm 1 starts with a random acyclic vertex set, \(CF\); then, a possibly better acyclic vertex set is obtained by addingor removing more than one vertex. Therefore, it is called the variable depth local search, and it can be applied to other heuristic algorithms, such as simulated annealing. Compared with the simple local search algorithm, where only one vertex would be added or removed to change the current solution, the variable depth local search operates more vertices and provides more efficiency in searching for the desired acyclic vertex set.