Volume 64, Issue 4 pp. 339-356

Research Article

A memetic algorithm for the weighted feedback vertex set problem

Francesco Carrabs,

Corresponding Author

Francesco Carrabs

Department of Mathematics, University of Salerno, Via Giovanni Paolo II, 132-84084-Fisciano (SA), Italy

Correspondence to: F. Carrabs; e-mail: [email protected]Search for more papers by this author

Carmine Cerrone,

Carmine Cerrone

Department of Mathematics, University of Salerno, Via Giovanni Paolo II, 132-84084-Fisciano (SA), Italy

Search for more papers by this author

Raffaele Cerulli,

Raffaele Cerulli

Department of Mathematics, University of Salerno, Via Giovanni Paolo II, 132-84084-Fisciano (SA), Italy

Search for more papers by this author

Francesco Carrabs,

Corresponding Author

Francesco Carrabs

Department of Mathematics, University of Salerno, Via Giovanni Paolo II, 132-84084-Fisciano (SA), Italy

Correspondence to: F. Carrabs; e-mail: [email protected]Search for more papers by this author

Carmine Cerrone,

Carmine Cerrone

Department of Mathematics, University of Salerno, Via Giovanni Paolo II, 132-84084-Fisciano (SA), Italy

Search for more papers by this author

Raffaele Cerulli,

Raffaele Cerulli

Department of Mathematics, University of Salerno, Via Giovanni Paolo II, 132-84084-Fisciano (SA), Italy

Search for more papers by this author

First published: 11 November 2014

https://doi.org/10.1002/net.21577

Citations: 10

Share a link

Email
Wechat
Bluesky

Abstract

Given an undirected and vertex weighted graph $urn:x-wiley:00283045:media:net21577:net21577-math-0001$ , the Weighted Feedback Vertex Set Problem consists of finding the subset $urn:x-wiley:00283045:media:net21577:net21577-math-0002$ of vertices, with minimum weight, whose removal results in an acyclic graph. Finding the minimum feedback vertex set in a graph is an important combinatorial problem that has a variety of real applications. In this article, we introduce a memetic algorithm for this problem. We propose an efficient greedy procedure that quickly generates chromosomes with specific characteristics and a wise application of recent local search procedures based on k-diamonds. Computational results show that the proposed algorithm outperforms the effectiveness of two other metaheuristics recently proposed in the literature for this problem. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(4), 339–356 2014

REFERENCES

1 V. Bafna, P. Berman, and T. Fujito, A 2-approximation algorithm for the undirected feedback vertex set problem, SIAM J Discrete Math 12 (1999), 289–297.
10.1137/S0895480196305124
Web of Science® Google Scholar
2 R. Bar-Yehuda, D. Geiger, J. Naor, and R.M. Roth, Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference, SIAM J Comput 27 (1998), 942–959.
10.1137/S0097539796305109
Web of Science® Google Scholar
3 A. Becker and D. Geiger, Approximation algorithms for the loop cutset problem, Proceeding of Tenth Conference on Uncertainty in Artificial Intelligence Research, Morgan Kaufmann, Seattle, USA, 1994, pp. 60–68.
Google Scholar
4 L. Brunetta, F. Maffioli, and M. Trubian, Solving the feedback vertex set problem on undirected graphs, Discrete Appl Math 101 (1999), 37–51.
10.1016/S0166-218X(99)00180-8
Web of Science® Google Scholar
5 F. Carrabs, R. Cerulli, M. Gentili, and G. Parlato, Minimum weighted feedback vertex set on diamonds, Electron Notes Discrete Math 17 (2004), 87–91.
10.1016/j.endm.2004.09.001
Google Scholar
6 F. Carrabs, R. Cerulli, M. Gentili, and G. Parlato, A linear time algorithm for the minimum weighted feedback vertex set on diamonds, Inf Process Lett 94 (2005), 29–35.
10.1016/j.ipl.2004.12.008
Web of Science® Google Scholar
7 F. Carrabs, R. Cerulli, M. Gentili, and G. Parlato, A tabu search heuristic based on k-diamonds for the weighted feedback vertex set problem, Lect Notes Comput Sci 6701 (2011), 589–602.
10.1007/978-3-642-21527-8_66
Web of Science® Google Scholar
8 M. Dell'Amico, A. Lodi, and F. Maffioli, Solution of the cumulative assignment problem with a well-structured tabu search method, J Heuristics 5 (1999), 123–143.
10.1023/A:1009647225748
Web of Science® Google Scholar
9 G. Even, J. Naor, B. Schieber, and L. Zosin, Approximating minimum subset feedback sets in undirected graphs with applications, SIAM J Discrete Math 13 (2000), 255–267.
10.1137/S0895480195291874
Web of Science® Google Scholar
10 P. Festa, P.M. Pardalos, and M.G.C. Resende, “Feedback set problems,” Encyclopedia of optimization, Springer, New York, 2009.
Google Scholar
11 R. Focardi, F.L. Luccio, and D. Peleg, Feedback vertex set in hypercubes, Inf Process Lett 76 (2000), 1–5.
10.1016/S0020-0190(00)00127-7
Web of Science® Google Scholar
12 P. Galinier, E. Lemamou, and M.W. Bouzidi, Applying local search to the feedback vertex set problem, J Heuristics 19(5) (2013), 1–22.
10.1007/s10732-013-9224-z
Web of Science® Google Scholar
13 W. Jiang, T. Liu, C. Wang, and K. Xu, Feedback vertex sets on restricted bipartite graphs, Theoretical Computer Science 507 (2013), 41–51.
10.1016/j.tcs.2012.12.021
Web of Science® Google Scholar
14 R.M. Karp, “Reducibility among combinatorial problems,” Complexity of computer computations, R.E. Miller and J.W. Thatcher, (Editors), New York, Plenum Press, 1972, pp. 85–103.
10.1007/978-1-4684-2001-2_9
Google Scholar
15 J. Kleinberg and A. Kumar, Wavelength conversion in optical networks, J Algorithms 38 (2001), 25–50.
10.1006/jagm.2000.1137
Web of Science® Google Scholar
16 Y.D. Liang, On the feedback vertex set problem in permutation graphs, Inf Process Lett 52 (1994), 123–129.
10.1016/0020-0190(94)00133-2
Web of Science® Google Scholar
17 Y.D. Liang and M.S. Chang, Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs, Acta Inform 34 (1997), 337–346.
10.1007/s002360050088
Web of Science® Google Scholar
18 E.L. Lloyd and M.L. Soffa, On locating minimum feedback vertex sets, J Comput Syst Sci 37 (1988), 292–311.
10.1016/0022-0000(88)90009-8
Web of Science® Google Scholar
19 C.L. Lu and C.Y. Tang, A linear-time algorithm for the weighted feedback vertex problem on interval graphs, Inf Process Lett 61 (1997), 107–111.
10.1016/S0020-0190(96)00193-7
Web of Science® Google Scholar
20 P. Moscato and C. Cotta, “A gentle introduction to memetic algorithms,” Handbook of metaheuristics, Vol. 7, F. Glover and G.A. Kochenberger (Editors), Springer, New York, 2003, pp. 105–144.
Google Scholar
21 P.M. Pardalos, T. Qian, and M.G.C. Resende, A greedy randomized adaptive search procedure for the feedback vertex set problem, J Comb Optim 2 (1999), 399–412.
10.1023/A:1009736921890
Web of Science® Google Scholar
22 D. Peleg, Local majority voting, small coalitions and controlling monopolies in graphs: A review, Proceedings of 3rd Colloquium on Structural Information and Communication Complexity, Siena, Italy, 1996.
Google Scholar
23 D. Peleg, Size bounds for dynamic monopolies, Discrete Appl Math 86 (1998), 263–273.
10.1016/S0166-218X(98)00043-2
Web of Science® Google Scholar
24 A. Shamir, A linear time algorithm for finding minimum cutsets in reduced graphs, SIAM J Comput 8 (1979), 645–655.
10.1137/0208051
Web of Science® Google Scholar
25 A. Takaoka, S. Tayu, and S. Ueno, On minimum feedback vertex sets in graphs, Proceedings of the 2012 3rd International Conference on Networking and Computing, ICNC 2012, Okinawa, Japan, 2012, pp. 429–434.
Web of Science® Google Scholar
26 C.C. Wang, E.L. Lloyd, and M.L. Soffa, Feedback vertex sets and cyclically reducible graphs, J Assoc Comput Mach 32 (1985), 296–313.
10.1145/3149.3159
Web of Science® Google Scholar

Citing Literature

Volume64, Issue4

Special Issue on Graph Algorithms and Optimization

December 2014

Pages 339-356

A memetic algorithm for the weighted feedback vertex set problem

Abstract

REFERENCES

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

A memetic algorithm for the weighted feedback vertex set problem

Abstract

REFERENCES

Citing Literature

References

Related

Information