{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:32:04Z","timestamp":1770064324144,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T00:00:00Z","timestamp":1736294400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T00:00:00Z","timestamp":1736294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hasso-Plattner-Institut f\u00fcr Digital Engineering gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multi-objective algorithms for the <jats:italic>W<\/jats:italic>-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most <jats:italic>W<\/jats:italic> vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution <jats:italic>OPT<\/jats:italic> and <jats:italic>W<\/jats:italic>. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the <jats:italic>W<\/jats:italic>-separator uses linear programming methods and requires non-trivial post-processing steps to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the <jats:italic>W<\/jats:italic>-separator problem.<\/jats:p>","DOI":"10.1007\/s00453-024-01290-9","type":"journal-article","created":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T18:09:16Z","timestamp":1736359756000},"page":"537-571","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator Problem"],"prefix":"10.1007","volume":"87","author":[{"given":"Samuel","family":"Baguley","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aneta","family":"Neumann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"Pappik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziena","family":"Zeif","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,8]]},"reference":[{"key":"1290_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (2012). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9"},{"key":"1290_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing Evolutionary Algorithms: The Computer Science Perspective","author":"Thomas Jansen","year":"2013","unstructured":"Jansen, Thomas: Analyzing Evolutionary Algorithms: The Computer Science Perspective. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)"},{"key":"1290_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16544-3","volume-title":"Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity","author":"Frank Neumann","year":"2010","unstructured":"Neumann, Frank, Witt, Carsten: Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer Berlin Heidelberg, Berlin, Heidelberg (2010)"},{"key":"1290_CR4","doi-asserted-by":"crossref","unstructured":"Doerr, B., Neumann, F.(eds.): Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer International Publishing, Cham (2020)","DOI":"10.1007\/978-3-030-29414-4"},{"key":"1290_CR5","doi-asserted-by":"publisher","unstructured":"Neumann, F., Sutton, A.M.: Parameterized complexity analysis of randomized search heuristics. In: Theory of Evolutionary Computation. Natural Computing Series, pp. 213\u2013248. Springer, (2020). https:\/\/doi.org\/10.1007\/978-3-030-29414-4_4","DOI":"10.1007\/978-3-030-29414-4_4"},{"issue":"4","key":"1290_CR6","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1007\/s00453-012-9660-4","volume":"65","author":"S Kratsch","year":"2013","unstructured":"Kratsch, S., Neumann, F.: Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica 65(4), 754\u2013771 (2013). https:\/\/doi.org\/10.1007\/s00453-012-9660-4","journal-title":"Algorithmica"},{"key":"1290_CR7","doi-asserted-by":"publisher","unstructured":"Kratsch, S., Lehre, P.K., Neumann, F., Oliveto, P.S.: Fixed parameter evolutionary algorithms and maximum leaf spanning trees: A matter of mutation. In: PPSN (1). Lecture Notes in Computer Science, vol. 6238, pp. 204\u2013213. Springer, (2010). https:\/\/doi.org\/10.1007\/978-3-642-15844-5_21","DOI":"10.1007\/978-3-642-15844-5_21"},{"issue":"4","key":"1290_CR8","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1162\/EVCO_a_00119","volume":"22","author":"AM Sutton","year":"2014","unstructured":"Sutton, A.M., Neumann, F., Nallaperuma, S.: Parameterized runtime analyses of evolutionary algorithms for the planar Euclidean traveling salesperson problem. Evol. Comput. 22(4), 595\u2013628 (2014). https:\/\/doi.org\/10.1162\/EVCO_a_00119","journal-title":"Evol. Comput."},{"key":"1290_CR9","doi-asserted-by":"publisher","unstructured":"Sutton, A.M., Neumann, F.: A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling. In: PPSN (1). Lecture Notes in Computer Science, vol. 7491, pp. 52\u201361. Springer, (2012). https:\/\/doi.org\/10.1007\/978-3-642-32937-1_6","DOI":"10.1007\/978-3-642-32937-1_6"},{"issue":"4","key":"1290_CR10","doi-asserted-by":"publisher","first-page":"1138","DOI":"10.1007\/s00453-021-00809-8","volume":"83","author":"AM Sutton","year":"2021","unstructured":"Sutton, A.M.: Fixed-parameter tractability of crossover: steady-state gas on the closest string problem. Algorithmica 83(4), 1138\u20131163 (2021). https:\/\/doi.org\/10.1007\/s00453-021-00809-8","journal-title":"Algorithmica"},{"key":"1290_CR11","doi-asserted-by":"publisher","unstructured":"Branson, L., Sutton, A.M.: Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems. In: FOGA, pp. 3\u20131310. ACM, (2021). https:\/\/doi.org\/10.1145\/3450218.3477304","DOI":"10.1145\/3450218.3477304"},{"key":"1290_CR12","doi-asserted-by":"publisher","unstructured":"Graph Separators, with Applications. Kluwer Academic Publishers, Boston (2002). https:\/\/doi.org\/10.1007\/b115747","DOI":"10.1007\/b115747"},{"issue":"2","key":"1290_CR13","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979). https:\/\/doi.org\/10.1137\/0136016","journal-title":"SIAM J. Appl. Math."},{"issue":"4","key":"1290_CR14","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1007\/s00453-016-0127-x","volume":"76","author":"PG Drange","year":"2016","unstructured":"Drange, P.G., Dregi, M.S., Hof, P.: On the computational complexity of vertex integrity and component order connectivity. Algorithmica 76(4), 1181\u20131202 (2016). https:\/\/doi.org\/10.1007\/s00453-016-0127-x","journal-title":"Algorithmica"},{"key":"1290_CR15","doi-asserted-by":"publisher","unstructured":"Casel, K., Friedrich, T., Issac, D., Niklanovits, A., Zeif, Z.: Balanced crown decomposition for connectivity constraints. In: 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference). LIPIcs, vol. 204, pp. 26\u201312615. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.26","DOI":"10.4230\/LIPIcs.ESA.2021.26"},{"key":"1290_CR16","doi-asserted-by":"publisher","unstructured":"Kumar, M., Lokshtanov, D.: A $$2 \\ell k$$ kernel for $$\\ell $$-component order connectivity. In: Guo, J., Hermelin, D. (eds.) 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark. LIPIcs, vol. 63, pp. 20\u201312014. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2016). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.20","DOI":"10.4230\/LIPIcs.IPEC.2016.20"},{"key":"1290_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/9781107415157","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019). https:\/\/doi.org\/10.1017\/9781107415157"},{"key":"1290_CR18","doi-asserted-by":"publisher","unstructured":"Casel, K., Friedrich, T., Niklanovits, A., Simonov, K., Zeif, Z.: Combining crown structures for vulnerability measures. CoRR abs\/2405.02378 (2024) https:\/\/doi.org\/10.48550\/ARXIV.2405.02378arXiv:2405.02378","DOI":"10.48550\/ARXIV.2405.02378"},{"issue":"3","key":"1290_CR19","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\\varepsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008). https:\/\/doi.org\/10.1016\/j.jcss.2007.06.019. (Computational Complexity 2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"1290_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-018-1255-7","volume":"177","author":"E Lee","year":"2019","unstructured":"Lee, E.: Partitioning a graph into small pieces with applications to path transversal. Math. Program. 177(1\u20132), 1\u201319 (2019). https:\/\/doi.org\/10.1007\/s10107-018-1255-7","journal-title":"Math. Program."},{"key":"1290_CR21","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.jcss.2017.04.004","volume":"88","author":"M Xiao","year":"2017","unstructured":"Xiao, M.: Linear kernels for separating a graph into components of bounded size. J. Comput. Syst. Sci. 88, 260\u2013270 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2017.04.004","journal-title":"J. Comput. Syst. Sci."},{"key":"1290_CR22","doi-asserted-by":"publisher","unstructured":"Baguley, S., Friedrich, T., Neumann, A., Neumann, F., Pappik, M., Zeif, Z.: Fixed parameter multi-objective evolutionary algorithms for the $$w$$-separator problem. In: Silva, S., Paquete, L. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2023, Lisbon, Portugal, pp. 1537\u20131545. ACM, (2023). https:\/\/doi.org\/10.1145\/3583131.3590501","DOI":"10.1145\/3583131.3590501"},{"key":"1290_CR23","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956). https:\/\/doi.org\/10.4153\/CJM-1956-045-","journal-title":"Can. J. Math."},{"key":"1290_CR24","doi-asserted-by":"publisher","unstructured":"Sudholt, D.: General lower bounds for the running time of evolutionary algorithms. In: Parallel Problem Solving from Nature - PPSN XI, 11th International Conference, Krak\u00f3w, Poland, September 11-15, 2010, Proceedings, Part I. Lecture Notes in Computer Science, vol. 6238, pp. 124\u2013133. Springer, (2010). https:\/\/doi.org\/10.1007\/978-3-642-15844-5_13","DOI":"10.1007\/978-3-642-15844-5_13"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01290-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01290-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01290-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,23]],"date-time":"2025-03-23T05:23:53Z","timestamp":1742707433000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01290-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,8]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["1290"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01290-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,8]]},"assertion":[{"value":"29 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no financial or proprietary interests in any material discussed in this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}