You are an expert at summarizing long articles. Proceed to summarize the following text: 
an undirected graph is formed by a set of vertices and a set of undirected edges , with each edge connecting between two different vertices . a feedback vertex set ( fvs ) for such a graph is a set of vertices intersecting with every cycle of the graph . in other words , the subgraph induced by the vertices outside the fvs contains no cycle ( it is a forest ) @xcite . the feedback vertex set problem aims at constructing a fvs of small cardinality for a given undirected graph . it is a fundamental nondeterministic polynomial - complete ( np - complete ) combinatorial optimization problem with global cycle constraints @xcite . in terms of complete algorithms , whether a graph @xmath0 has a fvs of cardinality smaller than @xmath1 can be determined in time @xmath2 @xcite . and an fvs of cardinality at most two times the optimal value can be easily constructed by an efficient polynomial algorithm @xcite . an optimal fvs is a feedback vertex set whose cardinality is the global minimum value among all the feedback vertex sets of the graph . for a given graph , an optimal fvs can be constructed in an exact way in time @xmath3 @xcite , where @xmath4 denotes the total number of vertices in the graph . applied mathematicians have obtained rigorous lower and upper bounds for the optimal fvs problem @xcite and have proved its tractability for graphs with specific structures ( see for example , @xcite and references cited therein ) .    due to the np - complete nature of the fvs problem , in general it is not feasible to construct optimal feedback vertex sets for large cycle - rich graphs . an important question is then to design efficent heurstic algorithms that are able to obtain near - optimal fvs solutions for given graph instances . such a task is quite nontrivial . a major technical difficulty is that cycles are global objects of a graph and therefore the existence of cycles can not be judged by checking only the neighborhood of a vertext . ( similar difficulties exist in other combinatorial optimization problems with global constraints , such as the steiner tree problem @xcite and the optimal routing problem @xcite . ) in ref . @xcite , one of the authors succeeded in converting the fvs problem to a spin glass problem with local interactions . the fvs problem was then studied from the spin glass perspective , and a message - passing algorithm , belief propagation - guided decimaton ( bpd ) , was impletmented to solve the fvs problem heuristically for single graph instances . this bpd algorithm is quite efficient in terms of computing time and computer memory ( since there is no need of cycle checking ) , and it can obtain fvs solutions that are very close to the optimal ones when applied on large random graph instances and regular lattices @xcite .    for the undirected fvs problem it is not yet known whether simple local search algorithms can achieve equally excellent results as the bpd algorithm . motivated by this question , we complement the message - passing approach in this paper by implementing and testing a simulated annealing local searching ( sals ) protocol @xcite for the undirected fvs problem . a similar algorithmic study has already been undertaken in @xcite for directed graphs . here we modify the microscopic search rules of @xcite to make it applicable to undirected graphs . in the sals algorithm , an order is defined for the vertices outside the focal fvs , and this order is constrained by a set of local vertex constraints . our simulation results suggest that this local search algorithm is comparable in performance to the bpd algorithm at least for random graph instances . the feedback vertex set problem has wide practical applications in the field of computer science ( such as integrated circuit design and database management ) . although not yet seriously explored , the fvs problem may have many potential applications in complex systems research as well . for example , if a vertex is contained in a large fraction of the near - optimal feedback vertex sets , we may expect this vertex to play a very significant role for the dynamical processes on the graph . therefore the probability of belonging to a near - optimal fvs can serve as a centrality index of dynamical significance for each vertex of a graph . such a probablity can be computed by sampling many independent near - optimal fvs solutions or be computed directly using the belief propagation iterative equations @xcite . the construction of a near - optimal fvs also facilitates the study of a complex dynamical system as a simpler response problem of a cycle - free subsystem ( which is intrinsically simple ) under the influence of the vertices in the fvs vertices . if the subgraph induced by the vertices in the fvs itself contains many cycles , such a decomposition can be applied on this subgraph again . through this iterated process , an initial cycle - rich complex graph is then organized into a hierarchy of forest ( cycle - free ) subgraphs and the edges between these forests . a simple illustration of this hierarchical organization is shown in fig .  [ fig : fvshierarchy ] . we believe such a hierarchical representation of a complex graph will be very helpful in future dynamical applications . ( color online ) . the four filled points form an optimal feedback vertex set for this graph @xmath0 . the subgraph @xmath5 induced by these four vertices and the cycle - free subgraph induced by all the remaining vertices ( shown as open points ) are connected through many edges ( shown in light blue ) . since the subgraph @xmath5 still contains cycles within itself , we decompose it into a tree subgraph of three vertices ( filled magenta points ) and a subgraph formed by a fvs of one vertex ( the central red point ) . by this way , the vertices in the orginal graph @xmath0 are arranged into three different layers . the vertices of each layer form a cycle - free subgraph ( a tree or a forest ) , while different layers are connected by edges . an important property of such an organization is that each cycle must involves vertices from at least two layers . , scaledwidth=35.0% ]    the next section describes the sals algorithm in detail , and in sec . 3 we test the performance of this local search algorithm on random graph instances and compare the results with the results obtained by the bpd algorithm and those obtained by the replica - symmetric mean field theory . we conclude this work in sec . the two appendices are the proofs of the theorems of sec .  2 . for a graph @xmath0 of @xmath4 vertices , let us consider an ordered list @xmath6 formed by @xmath7 vertices of this graph @xmath8 following @xcite , we assign to the first vertex @xmath9 of this list an integer rank @xmath10 , to the second vertex an integer rank @xmath11 , ... , and to the last vertex @xmath12 an integer rank @xmath13 . therefore each vertex @xmath14 has an integer rank @xmath15 which marks the position of this vertex in the list @xmath6 . for the purpose of the fvs problem , we introduce for each vertex @xmath14 a ranking condition as @xmath16 where @xmath17 denotes an edge of the graph @xmath0 between vertex @xmath18 and vertex @xmath19 , and @xmath20 if @xmath21 and @xmath22 if @xmath23 . the ranking condition ( [ eq : rc ] ) is satisfied by vertex @xmath18 if and only if among all the nearest neighboring vertices of vertex @xmath18 that are also contained in the list @xmath6 , at most one of them has a lower rank than that of @xmath18 . a list @xmath6 is referred to as a legal list if all its vertices satisfy the ranking condition ( [ eq : rc ] ) . the link between legal lists and feedback vertex sets is setup by the following two theorems :    [ th:1 ] if @xmath6 is a legal list , then the subgraph of the graph @xmath0 induced by all the vertices of this list is cycle - free . therefore the set @xmath24 formed by all the remaining vertices of @xmath0 not included in @xmath6 is a fvs . [ th:2 ] if @xmath24 is a fvs for a graph @xmath0 , then it is possible to form a legal list @xmath6 using all the vertices not contained in @xmath24 . these two theoretms are easy to prove , see the appendices for technical details . they suggest that there is a one - to - many correspondance between a fvs @xmath24 and legal lists @xmath6 . therefore the problem of constructing an optimal fvs is converted to a problem of constructing a legal list @xmath6 of maximal cardinality . notice that judging whether a list @xmath6 is legal or not is algorithmically very easy as eq . ( [ eq : rc ] ) involves only the neighborhood a focal vertex @xmath18 but not the connection pattern of the whole graph @xmath0 . a similar conversion from global constraints to local constraints has also been used in the steiner tree problem , which aims at constructing a tree of minimal total edge length connecting a set of specified vertices @xcite .    just for simplicity of later discussions , let us define the energy of a legal list @xmath6 as the total number of vertices not contained in it , namely @xmath25 in otherwords , @xmath26 is just the cardinality of the complementary fvs @xmath24 of the list @xmath6 . following ref . @xcite we implement a simulated annealing local search algorithm as follows :    1 . input the graph @xmath0 . initialize the legal set @xmath6 as containing only a single randomly chosen vertex of @xmath0 , and the complementary feedback vertex set @xmath24 then contains all the other vertices of @xmath0 . set the temperature @xmath27 to an initial value @xmath28 . 2 .   choose a vertex ( say @xmath18 ) uniformly at random from the feedback vertex set @xmath24 . + \(a ) if the list @xmath6 contains no nearest neighbor of the vertex @xmath18 , delete @xmath18 from @xmath24 and insert it to the head of @xmath6 . then vertex @xmath18 has rank @xmath29 in the updated list @xmath6 and the energy of @xmath6 decreases by @xmath30 . + \(b ) if @xmath6 contains exactly one nearest neighbor ( say @xmath19 with rank @xmath31 ) of the vertex @xmath18 , delete @xmath18 from @xmath24 and insert it to @xmath6 at the position just after vertex @xmath19 . then vertex @xmath18 has rank @xmath32 in the updated list @xmath6 and the energy of @xmath6 decreases by @xmath30 . + \(c ) if @xmath6 contains two or more nearest neighbors ( say @xmath33 with vertex @xmath19 having the lowest rank @xmath31 among these vertices ) of the vertex @xmath18 , we make a proposal of moving @xmath18 from @xmath24 to the ordered list @xmath6 at the position just after vertex @xmath19 and deleting all those nearest neighbors of @xmath18 from @xmath6 if the insertion of @xmath18 causes the violation of the ranking condition ( [ eq : rc ] ) for these vertices . suppose @xmath34 vertices have to be deleted from @xmath6 ( and be added to @xmath24 ) as a result of inserting vertex @xmath18 to @xmath6 , then the energy increase of @xmath6 is @xmath35 . if @xmath36 we accept the proposed action with probability @xmath30 , otherwise we accept it with probability @xmath37 . if this proposal is accepted , then vertex @xmath18 has rank @xmath32 in the updated list @xmath6 . repeat step 1 until the list @xmath6 has been successfully updated for @xmath38 times . during this process , record the best fvs so far reached and the corresponding lowest energy , @xmath39 . 4 .   decrease the temperature to @xmath40 , where @xmath41 is a fixed constant , and then repeat steps 1 - 2 . if the energy value @xmath39 does not change in @xmath42 contiguous temperature stages , then we stop the local search process and output the reached best fvs .    in our computer experiments we use @xmath43 , @xmath44 and @xmath45 which are identical to the values used in ref . the temperature ratio @xmath46 is set to several different values @xmath47 , @xmath48 and @xmath49 . as shown in fig .  2 , the slower the rate of temperature decrease , the lower is the energy of the constructed best fvs solutions . the bpd algorithm was applied to erds - renyi ( er ) random graphs and regular ( rr ) random graphs in @xcite to test its performance . as we want to compare the performance of the present sals algorithm with the bpd algorithm , we apply the sals algorithm on the same er and rr random graphs used in @xcite . an er random graph of @xmath4 vertices and @xmath50 edges was generated in @xcite by first selecting @xmath51 different vertex pairs uniformly at random from the whole set of @xmath52 candidate vertex pairs and then connecting the two vertices of each selected vertex pair by an edge . a vertex in such a graph has on average @xmath53 nearest neighbors ( i.e. , the mean vertex degree of the graph is @xmath53 ) . when @xmath54 the vertex degree distribution of the graph converges to a poisson distribution of mean value @xmath53 @xcite . a rr graph differs from an er graph with the additional constraint that each vertex has exactly the same number @xmath53 of nearest neighbors ( here @xmath53 must be an integer ) . it was generated by first attaching to each vertex a number of @xmath53 half - edges and then randomly connecting two half - edges into a full edge , but prohibiting self - loops or multiple edges between the same pair of vertices ( see ref . @xcite for more details of the graph generation process ) . the vertex number of all these random graph instances is equal to the same value @xmath55 . there are @xmath56 independently generated er or rr random graph instances at each fixed ( mean ) degree value @xmath53 . we run the sals process once on each of these @xmath56 instances and then compare the mean value of the obtained final @xmath39 values with the mean value of the final energies obtained in @xcite by running the bpd process once on each of these @xmath56 graph instances .    the evolution of the minimal energy @xmath39 as a function of the temperature @xmath27 is shown in fig .  [ fig : evolution ] for er ( a ) and rr ( b ) random graphs of @xmath57 . when @xmath58 the evolution curves for the three different cooling parameters @xmath49 , @xmath59 and @xmath60 coincide with each other . this indicates that at @xmath58 the typical relaxation time of energy is shorter than the time scale of temperature decreasing . at @xmath61 the curve of @xmath49 starts to separate from the other two curves , and the final value of @xmath39 is considerably higher than those of the other two evolutionary trajectories . this indicates that at cooling parameter @xmath49 the simulated annealing process is eventually trapped in a local region of the configuration space whose energy minimal value is extensively higher than that of the optimal solutions . the two evolutionary curves of @xmath62 and @xmath47 again separate from each other at a lower temperature of @xmath63 , and the final value of @xmath39 reached at cooling parameter @xmath47 is slightly lower than the final value of @xmath39 reached at @xmath62 . if the value of @xmath46 is set to be more closer to @xmath30 the final value of @xmath39 will decrease slightly further ( at the expense of much longer simulation times ) . the observation that lower final energy values can be reached by lowering the cooling rate strongly indicates the system has a very complicated low - energy landscape with many local minima . this is consistent with the prediction that the undirected fvs problem is in a spin glass phase at low enough energy values @xcite . figure  [ fig : fvs ] compares the performance of the sals algorithm ( the cooling parameter fixed to @xmath47 ) with that of the bpd algorithm on er ( a ) and rr ( b ) random graphs . we see that bpd slightly outperforms sals for both ensembles of random graphs this is not surprising , since the bpd algorithm takes into account the global structure of the graph through message - passing , while the sals algorithm considers only the local graph structure . it is interesting to see that the results of the two algorithms are actually very close to each other , especially for er random graphs . as also shown in fig . [ fig : fvs ] , at each value of ( mean ) degree @xmath53 , the result obtained by the sals algorithm is very close to the predicted value of the global minimal energy by the replica - symmetric mean field theory @xcite . therefore message - passing algorithms are not the only candidate choices to construct near - optimal feedback vertex sets for undirected random graphs . an advantage of the sals algorithm is that its implementation is very straightforward . it may be the method of choice for many practical applications .    , a vertex s probability of being in a feedback vertex set increases with its vertex degree @xmath64 . each star point is the mean result obtained by averaging over the @xmath56 final fvs solutions obtained by the sals algorithm on the @xmath56 random graph instances of @xmath55 vertices . each plus point denotes the result obtained by the rs mean field theory at @xmath65 @xcite . , scaledwidth=35.0% ]    we also notice from fig . [ fig : fvs ] that the sals algorithm performs poorer in regular random graphs than in er random graphs . this is probably due to the following fact : each vertex in a regular random graph has the same degree so there is local guide as to whether a vertex should be included into the feedback vertex set or not . on the other hand the degree heterogeneity of an er graph will give some local guide to the sals process to arrive at a near - optimal fvs . based on the final @xmath56 fvs solutions obtained by the sals algorithm on the @xmath56 er random graphs with mean vertex degree @xmath57 , we compute the mean probability @xmath66 that a vertex of degree @xmath64 is contained in the fvs . the results shown in fig . [ fig : vertexfvsprob ] demonstrate that @xmath66 is close to @xmath67 for @xmath68 and close to @xmath30 for @xmath69 , and it is an rapidly increasing function of @xmath64 in the range of @xmath70 . the empirically obtained mean value of @xmath66 is found to be very close to the value of @xmath66 computed using the replica - symmetric mean field theory . notice that for @xmath71 the empirical values of @xmath66 are slightly larger than those predicted by the rs mean field . such small differences cause the energies of the construsted fvs solutions to be higher than the corresponding optimal values . the graphs for real - world complex systems usually are highly heterogenous in terms of vertex degree distributions @xcite . therefore it is very likely that the sals algorithm to have very good performance for such graphs . in this paper , we implemented and tested a local search algorithm for the undirected feedback vertex set problem . similar to the local search algorithm for the directed fvs problem @xcite , our algorithm uses the technique of simulated annealing to explore the highly complex landscape of low - energy congiurations . our simulation results demonstrated that this algorithm is very efficient for large random graph instances . the relative sizes of the constructed fvs solutions by the local search algorithm are very close to the predicted values of the replica - symmetric mean field theory , and they are also very similar to the results obtained by the bpd message - passing algorithm .    it should be emphasized that the microscopic dynamical rules of our local search algorithm do not obey the detailed balance condition . these dynamical rules therefore need to be appropriately modified if one is interested in the equilibrial fvs solutions at a given fixed temperature @xmath27 . we are currently using a modified set of microscopic dynamical rules to study the spin glass phase transition of the model proposed in @xcite . such an equilibrium study will offer more physical insights on the cooling - rate dependent behaviors of fig . [ fig : evolution ] . the numerical simulations were performed at the hpc computer cluster of the authors institute . this work was partially supported by the national basic research program of china ( no . 2013cb932804 ) , the knowledge innovation program of chinese academy of sciences ( no .  kjcx2-ew - j02 ) , and the national science foundation of china ( grant nos .  11121403 , 11225526 ) . hjz conceived research ; smq performed research ; hjz wrote the paper . consider a generic legal list @xmath6 formed by some vertices of the graph @xmath0 , see eq . ( [ eq : glist ] ) . let us consider the subgraph @xmath72 induced by all the vertices of list @xmath6 and all the edges between these vertices . since @xmath6 is a legal list , every vertex @xmath14 must satisfy the rank condition ( [ eq : rc ] ) . consequently , every vertex in the subgraph @xmath72 has at most one nearest neighbor with rank lower than that of itself . this subgraph @xmath72 must be cycle - free . we prove this statement by contradiction . assume there is a cycle in the subgraph @xmath72 involving @xmath64 vertices : @xmath73 if the rank of vertex @xmath74 is lower than that of @xmath75 , then due to the fact of vertex @xmath75 having at most one nearest neighbor with lower rank than itself , the rank of @xmath76 must be higher than that of @xmath75 . continuing this analysis along the cycle , we obtain that the rank of vertex @xmath77 must be higher than that of @xmath78 but lower than that of @xmath74 . but this is impossible since the rank of @xmath78 must be higher than that of @xmath74 . similarly , if the rank of vertex @xmath74 is higher than that of @xmath75 , we will arrive at the contradicting results that the rank of @xmath75 is higher than that of @xmath79 while the rank of @xmath79 is higher than that of @xmath74 . because of these contradictions , the assumption of @xmath72 containing a cycle must be false . therefore @xmath72 must be a tree or a forest . then the set @xmath24 formed by the vertices not contained in @xmath6 must be a feedback vertex set . suppose the set @xmath24 is a fvs of a graph @xmath0 . then the subgraph @xmath72 induced by all the vertices not included in @xmath24 must be cycle - free . if @xmath72 has only one connected component ( i.e. , being a tree ) , we can pick a vertex ( say @xmath18 ) of @xmath72 uniformly at random and specify this vertex as the root of the tree subgraph @xmath72 . we can then construct an ordered list @xmath6 using all the vertices of @xmath72 in such a way : first the root vertex @xmath18 , then all the vertices of unit path length to @xmath18 ( in random order ) , followed by all the vertices of path length two to @xmath18 ( again in random order ) , ... , followed by the remaining vertices of the longest path length to @xmath18 ( in random order ) . obviously @xmath6 is a legal list with the ranking condition ( [ eq : rc ] ) satisfied for all its vertices . if @xmath72 is a forest with two or more tree components , we can perform the above - mentioned process for each of its tree components and then contatenate the constructed ordered lists in a random order to form a whole ordered list @xmath6 . this list @xmath6 must also be a legal list .
an undirected graph consists of a set of vertices and a set of undirected edges between vertices . 
 such a graph may contain an abundant number of cycles , then a feedback vertex set ( fvs ) is a set of vertices intersecting with each of these cycles . constructing a fvs of cardinality approaching 
 the global minimum value is a optimization problem in the nondeterministic polynomial - complete complexity class , therefore it might be extremely difficult for some large graph instances . in this paper 
 we develop a simulated annealing local search algorithm for the undirected fvs problem . by defining an order for the vertices outside the fvs 
 , we replace the global cycle constraints by a set of local vertex constraints on this order . under these local constraints 
 the cardinality of the focal fvs is then gradually reduced by the simulated annealing dynamical process . 
 we test this heuristic algorithm on large instances of erdos - renyi random graph and regular random graph , and find that this algorithm is comparable in performance to the belief propagation - guided decimation algorithm .