Skip to main content
SpringerLink
Log in

Applying local search to the feedback vertex set problem

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

The feedback vertex set problem (FVSP) consists in making a given directed graph acyclic by removing as few vertices as possible. In spite of the importance of this NP-hard problem, no local search approach had been proposed so far for tackling it. Building on a property of acyclic graphs, we suggest in this paper a new representation of the solutions of the FVSP (feedback sets). Thanks to this solution representation, we are able to design a local transformation (equivalent to a neighborhood) that changes a feedback set into a new one. Based on this neighborhood, we have developed a simulated annealing algorithm for the FVSP. Our experiments show that our algorithm outperforms the best existing heuristic, namely the greedy adaptive search procedure by Pardalos et al.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  • AT &T Labs: Personal page of Mauricio Resende at AT &T Labs. http://www2.research.att.com/~mgcr/. Accessed Mar 2013

  • Bafna, V., Berman, P., Fujito, T.: Approximating feedback vertex set for undirected graphs within ratio 2, manuscript (1994)

  • Becker, A., Geiger, G.: Approximation algorithms for the loop cutset problem. In: Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence, pp. 60–68 (1979)

  • Cerny, V.: Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45, 41–51 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  • Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 6, 109–133 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  • Festa, P., Pardalos, P.M., Resende, M.G.C.: Algorithm 815: FORTRAN subroutines for computing approximate solutions of feedback set problems using GRASP. ACM Trans. Math. Softw. 27(4), 456–464 (2001)

    Article  MATH  Google Scholar 

  • Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of optimization, pp. 1005–1016. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  • Garey, M.R., Johnson, D.S.: Computers and reducibility: a guide to the theory of NP-completeness. W.H. Freeman, San Francisco (1979)

    MATH  Google Scholar 

  • Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  • Levy, H., Low, D.W.: A contraction algorithm for finding small cycle cutsets. J. Algorithms 9(4), 470–493 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  • Lin, H.M., Jou, J.Y.: Computing minimum feedback vertex sets by contraction operations and its applications on CAD. In: (ICCD ’99) International Conference on Computer Design, pp. 364–369 (1999)

  • Monien, B., Schultz, R.: Four approximation algorithms for the feedback vertex set problem. In: Proceedings of the 7th Conference on Graph Theoretic Concepts of Computer Science, pp. 315–390 (1981)

  • Morgenstern, C.: Distributed coloration neighborhood search. In: Johnson, D., Trick, M. (eds.) Cliques, coloring, and satisfiability, DIMACS: series in discrete mathematics and theoretical computer science, vol. 26, pp. 335–357. American Mathematical Society, New Providence (1996)

    Google Scholar 

  • Pardalos, P.M., Qian, T., Resende, M.G.C.: A greedy randomized adaptive search procedure for feedback vertex set. J. Comb. Optim. 2, 399–412 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  • Qian, T., Ye, Y., Pardalos, P.M.: A pseudo-approximation algorithm for FVS. In: Floudas, C., Pardalos, P. (eds.) State of the art in global optimization, pp. 341–351. Kluwer Academic Publishers, Dordrecht, Boston, London (1996)

    Chapter  Google Scholar 

  • Seymour, P.D.: Packing directed circuits fractionally. Combinatorica 15, 182–188 (1995)

    Article  MathSciNet  Google Scholar 

  • The New York Times: New ’micros’ disclosed. The New York Times, 28 Jan 1993

  • Wikipedia. http://en.wikipedia.org/wiki/SGI_Challenge. Accessed Mar 2013

  • Yannakakis, M.: Node and edge-deletion NP-complete problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 253–264 (1978)

  • Yehuda, B., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and Bayesian inference. In: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 344–354 (1994)

Download references

Author information

Authors and Affiliations

  1. Ecole Polytechnique de Montréal, Montreal, QC, Canada

    Philippe Galinier, Eunice Lemamou & Mohamed Wassim Bouzidi

Authors
  1. Philippe Galinier
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eunice Lemamou
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mohamed Wassim Bouzidi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Philippe Galinier.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Galinier, P., Lemamou, E. & Bouzidi, M.W. Applying local search to the feedback vertex set problem. J Heuristics 19, 797–818 (2013). https://doi.org/10.1007/s10732-013-9224-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-013-9224-z

Keywords

Search

Navigation