## 1 Introduction  
Inspired by many deadlock detection applications, the Feedback Vertex Set Problem (FVSP) is known to be NP-complete and plays an important role in the study of deadlock recovery [1, 2]. For example, the wait-for graph is a directed graph used for deadlock detection in operating systems and relational database systems of an operating system. and each directed cycle corresponds to a deadlock situation in the wait-for graph. In order to resolve all deadlocks, some blocked processes need to be aborted. A minimum feedback vertex set in this graph corresponds to a minimum number of processes that one needs to abort. Therefore solving the FVSP with more efficiency and better performance can contribute to an improved deadlock recovery. To describe the FVSP, the following concepts are predefined. Assuming \(G=(V(G),E(G))\) is a graph, then the set of vertices is denoted by \(V(G)\), and the set of edges of \(G\) is denoted by \(E(G)\). For \(S\subseteq V(G)\), the subgraph induced by \(S\) is denoted by \(G[S]\). The set of vertices adjacent to a vertex, \(i\in V(G)\), will be denoted by \(N(i)=\{j\in V(G):(i,j)\in E\}\) and called the \(openneighborhood\) of the vertex, \(i\). Let \(G\) be a graph. A feedback vertex set, \(S\), in \(G\) is a set of vertices in \(G\), whose removal results in a graph without cycle (or equivalently, every cycle in \(G\) contains at least one vertex in \(S\)). The FVSP can be considered in both directed and undirected graphs.Let \(G\) be an undirected graph. A Feedback Vertex Set Problem (FVSP), \(S\), in \(G\) is a set of vertices in \(G\), whose removal results in a graph without cycle (or equivalently, every cycle in \(G\) contains at least one vertex in \(S\)). Let \(G\) be a directed graph. A feedback vertex set (FVS), \(S\), in \(G\) is a set of vertices in \(G\), whose removal results in a graph without directed cycle (or equivalently, every directed cycle in \(G\) contains at least one vertex in \(S\)). Inspired by real world applications, several variants were proposed over the years. Some of them are summarized by the following definitions. **(a)**: **FVSP:**: Given a graph, \(G\), the feedback vertex set problem is to find an FVS with the minimum cardinality. **(b)**: **The Parameterized Feedback Vertex Set Problem (DFVSP):**: Given a graph, \(G\), and a parameter, \(k\), the Parameterized Feedback Vertex Set Problem is to either find an FVS of at most \(k\) vertices for \(G\) or report that no such set exists. **(c)**: **The Vertex Weighted Feedback Vertex Set Problem (VWFVSP):**: Given a vertex weighted graph, \(G\), the Vertex Weighted Feedback Vertex Set Problem is to find an FVS with the minimum weight. The Parameterized Feedback Vertex Set Problem is the decision version of the feedback vertex set problem. The FVSP and DFVSP were classic NP-complete problems that appeared in the first list of NP-complete problems in [PERSON]'s seminal paper [3]. When the edges or arcs instead of vertices are considered, it becomes the corresponding edge or arc version. For example, the parameterized feedback arc set problem is to find out whether there is a minimum of \(k\) arcs in a given graph, whose removal makes the graph acyclic. Let \(G\) be a graph. It is said that a vertex set, \(S\), is an _acyclic vertex set_ if \(G[S]\) is acyclic. An acyclic vertex set, \(S\), is _maximal_ if \(G[S\cup\{v\}]\) is not acyclic for any \(v\in V(G)\setminus S\). Note that if \(G[S]\) is acyclic, then \(V(G)\setminus S\) is a feedback vertex set. Without loss of generality, only the feedback vertex set problem for an undirected graph is considered in this paper, and the aim is to search for the largest subset, \(S\subseteq V(G)\), such that \(G[S]\) is acyclic. The rest of this paper is organized as follows: Section 2 presents the related work of local search heuristics. Then, Sections 3 and 4 propose the \(k\)-opt local search (KLS)-based local search algorithm and the KLS with a randomized scheme algorithm in detail.