{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:55:45Z","timestamp":1777362945919,"version":"3.51.4"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,5,24]],"date-time":"2025-05-24T00:00:00Z","timestamp":1748044800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,24]],"date-time":"2025-05-24T00:00:00Z","timestamp":1748044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/X030989\/1"],"award-info":[{"award-number":["EP\/X030989\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,3]]},"abstract":"Abstract<\/jats:title>\n \n The Maximum Leaf Spanning Arborescence problem (MLSA) in directed acyclic graphs (dags) is defined as follows: Given a directed acyclic graph\n G<\/jats:italic>\n and a vertex\n \n \n $$r\\in V(G)$$<\/jats:tex-math>\n \n \n r<\/mml:mi>\n \u2208<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n from which every other vertex is reachable, find a spanning arborescence rooted at\n r<\/jats:italic>\n maximizing the number of leaves (vertices with out-degree zero). The MLSA in dags is known to be APX-hard as reported by Nadine Schwartges, Spoerhase, and Wolff (Approximation and Online Algorithms, Springer, Berlin Heidelberg, 2012) and the best known approximation guarantee of\n \n \n $$\\frac{7}{5}$$<\/jats:tex-math>\n \n \n 7<\/mml:mn>\n 5<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is due to Fernandes and Lintzmayer (J. Comput. Syst. Sci. 135: 158\u2013174,2023): They prove that any\n \n \n $$\\alpha $$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation for the\n hereditary<\/jats:italic>\n 3-\n set packing problem<\/jats:italic>\n , a special case of weighted 3-set packing, yields a\n \n \n $$\\max \\{\\frac{4}{3},\\alpha \\}$$<\/jats:tex-math>\n \n \n max<\/mml:mo>\n {<\/mml:mo>\n \n 4<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n ,<\/mml:mo>\n \u03b1<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation for the MLSA in dags, and provide a\n \n \n $$\\frac{7}{5}$$<\/jats:tex-math>\n \n \n 7<\/mml:mn>\n 5<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation for the hereditary 3-set packing problem. In this paper, we improve upon this result by providing a\n \n \n $$\\frac{4}{3}$$<\/jats:tex-math>\n \n \n 4<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation for the hereditary 3-set packing problem, and, thus, the MLSA in dags. The algorithm that we study is a simple local search procedure considering swaps of size up to 10 and can be analyzed via a two-stage charging argument. We further provide a clear picture of the general connection between the MLSA in dags and set packing by rephrasing the MLSA in dags as a\n hereditary set packing problem<\/jats:italic>\n . With a much simpler proof, we extend the reduction by Fernandes and Lintzmayer and show that an\n \n \n $$\\alpha $$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation for the\n hereditary<\/jats:italic>\n k<\/jats:italic>\n -\n set packing problem<\/jats:italic>\n implies a\n \n \n $$\\max \\{\\frac{k+1}{k},\\alpha \\}$$<\/jats:tex-math>\n \n \n max<\/mml:mo>\n {<\/mml:mo>\n \n \n k<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n k<\/mml:mi>\n <\/mml:mfrac>\n ,<\/mml:mo>\n \u03b1<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation for the MLSA dags. On the other hand, we provide lower bound examples proving that our approximation guarantee of\n \n \n $$\\frac{4}{3}$$<\/jats:tex-math>\n \n \n 4<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is best possible for local search algorithms with constant improvement size.\n <\/jats:p>","DOI":"10.1007\/s10107-025-02233-0","type":"journal-article","created":{"date-parts":[[2025,5,24]],"date-time":"2025-05-24T04:03:36Z","timestamp":1748059416000},"page":"111-133","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A $$\\nicefrac {4}{3}$$-approximation for the maximum leaf spanning arborescence problem in DAGs"],"prefix":"10.1007","volume":"216","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3664-3687","authenticated-orcid":false,"given":"Meike","family":"Neuwohner","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,24]]},"reference":[{"issue":"1","key":"2233_CR1","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1137\/070710494","volume":"23","author":"Noga Alon","year":"2009","unstructured":"Alon, Noga, Fomin, Fedor V., Gutin, Gregory, Krivelevich, Michael, Saurabh, Saket: Spanning directed trees with many leaves. SIAM J. Discret. Math. 23(1), 466\u2013476 (2009). https:\/\/doi.org\/10.1137\/070710494","journal-title":"SIAM J. Discret. Math."},{"key":"2233_CR2","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344428","author":"Daniel Binkele-Raible","year":"2012","unstructured":"Binkele-Raible, Daniel, Fernau, Henning, Fomin, Fedor V., Lokshtanov, Daniel, Saurabh, Saket, Villanger, Yngve: Kernel(s) for problems with no kernel: on out-trees with many leaves. ACM Trans. Algorithms (2012). https:\/\/doi.org\/10.1145\/2344422.2344428","journal-title":"ACM Trans. Algorithms"},{"key":"2233_CR3","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.jda.2011.06.005","volume":"12","author":"Paul Bonsma","year":"2012","unstructured":"Bonsma, Paul: Max-leaves spanning tree is APX-hard for cubic graphs. J. Discrete Algorithms 12, 14\u201323 (2012). https:\/\/doi.org\/10.1016\/j.jda.2011.06.005","journal-title":"J. Discrete Algorithms"},{"key":"2233_CR4","doi-asserted-by":"crossref","unstructured":"Cygan, Marek: Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pp. 509\u2013518. IEEE Computer Society, (2013)","DOI":"10.1109\/FOCS.2013.61"},{"key":"2233_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-642-11269-0_7","volume-title":"Parameterized and Exact Computation","author":"Jean Daligault","year":"2009","unstructured":"Daligault, Jean, Thomass\u00e9, St\u00e9phan.: On finding directed trees with many leaves. In: Chen, Jianer, Fomin, Fedor V. (eds.) Parameterized and Exact Computation, pp. 86\u201397. Springer, Berlin Heidelberg (2009)"},{"key":"2233_CR6","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798599","author":"Matthew Drescher","year":"2010","unstructured":"Drescher, Matthew, Vetta, Adrian: An approximation algorithm for the maximum leaf spanning arborescence problem. ACM Trans. Algorithms (2010). https:\/\/doi.org\/10.1145\/1798596.1798599","journal-title":"ACM Trans. Algorithms"},{"key":"2233_CR7","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069b.013","volume":"69B","author":"Jack Edmonds","year":"1965","unstructured":"Edmonds, Jack: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bureau Stand. Sect. B Math. Math. Phys. 69B, 125\u2013130 (1965). https:\/\/doi.org\/10.6028\/jres.069b.013","journal-title":"J. Res. Nat. Bureau Stand. Sect. B Math. Math. Phys."},{"key":"2233_CR8","unstructured":"Erd\u0151s, Paul, Sachs, Horst: Regul\u00e4re Graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 12(3):251\u2013257 (1963)"},{"key":"2233_CR9","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.dam.2021.06.018","volume":"323","author":"Cristina G Fernandes","year":"2022","unstructured":"Fernandes, Cristina G., Lintzmayer, Carla N.: Leafy spanning arborescences in dags. Discret. Appl. Math. 323, 217\u2013227 (2022). https:\/\/doi.org\/10.1016\/j.dam.2021.06.018","journal-title":"Discret. Appl. Math."},{"key":"2233_CR10","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.jcss.2023.02.006","volume":"135","author":"Cristina G Fernandes","year":"2023","unstructured":"Fernandes, Cristina G., Lintzmayer, Carla N.: How heavy independent sets help to find arborescences with many leaves in dags. J. Comput. Syst. Sci. 135, 158\u2013174 (2023). https:\/\/doi.org\/10.1016\/j.jcss.2023.02.006","journal-title":"J. Comput. Syst. Sci."},{"key":"2233_CR11","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, Martin, Yu, Huiwen: Approximating the $$k$$-Set Packing Problem by Local Improvements. In: International Symposium on Combinatorial Optimization, pp. 408\u2013420. (2014)","DOI":"10.1007\/978-3-319-09174-7_35"},{"issue":"1","key":"2233_CR12","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0020-0190(94)90139-2","volume":"52","author":"G Galbiati","year":"1994","unstructured":"Galbiati, G., Maffioli, F., Morzenti, A.: A short note on the approximability of the maximum leaves spanning tree problem. Inf. Process. Lett. 52(1), 45\u201349 (1994). https:\/\/doi.org\/10.1016\/0020-0190(94)90139-2","journal-title":"Inf. Process. Lett."},{"key":"2233_CR13","unstructured":"Garey, Michael\u00a0R., Johnson, David\u00a0S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, (1990)"},{"issue":"4","key":"2233_CR14","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374\u2013387 (1998). https:\/\/doi.org\/10.1007\/PL00009201","journal-title":"Algorithmica"},{"key":"2233_CR15","doi-asserted-by":"crossref","unstructured":"Karp, Richard\u00a0M.: Reducibility among combinatorial problems. In Raymond\u00a0E. Miller, James\u00a0W. Thatcher, and Jean\u00a0D. Bohlinger, editors, Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations. Plenum Press, (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"2233_CR16","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"Sanjeev Khanna","year":"1998","unstructured":"Khanna, Sanjeev, Motwani, Rajeev, Sudan, Madhu, Vazirani, Umesh: On syntactic versus computational views of approximability. SIAM J. Comput. 28(1), 164\u2013191 (1998). https:\/\/doi.org\/10.1137\/S0097539795286612","journal-title":"SIAM J. Comput."},{"key":"2233_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-02026-3","author":"Meike Neuwohner","year":"2023","unstructured":"Neuwohner, Meike: The limits of local search for weighted k-set packing. Math. Prog. (2023). https:\/\/doi.org\/10.1007\/s10107-023-02026-3","journal-title":"Math. Prog."},{"key":"2233_CR18","doi-asserted-by":"crossref","unstructured":"Neuwohner, Meike: Passing the limits of pure local search for weighted k-set packing. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1090\u20131137. Society for Industrial and Applied Mathematics, (2023)","DOI":"10.1137\/1.9781611977554.ch41"},{"key":"2233_CR19","doi-asserted-by":"crossref","unstructured":"Neuwohner, Meike: A 4\/3-approximation for the maximum leaf spanning arborescence problem in dags. In Jens Vygen and Jaros\u0142aw Byrka, editors, Integer Programming and Combinatorial Optimization, volume 14679 of Lecture Notes in Computer Science, pp. 337\u2013350. Springer, (2024)","DOI":"10.1007\/978-3-031-59835-7_25"},{"issue":"1\u20133","key":"2233_CR20","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.tcs.2004.08.013","volume":"329","author":"Lu Ruan","year":"2004","unstructured":"Ruan, Lu., Hongwei, Du., Jia, Xiaohua, Weili, Wu., Li, Yingshu, Ko, Ker-I.: A greedy approximation for minimum connected dominating sets. Theoret. Comput. Sci. 329(1\u20133), 325\u2013330 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.08.013","journal-title":"Theoret. Comput. Sci."},{"key":"2233_CR21","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-29116-6_7","volume-title":"Approximation and Online Algorithms","author":"Nadine Schwartges","year":"2012","unstructured":"Schwartges, Nadine, Spoerhase, Joachim, Wolff, Alexander: Approximation algorithms for the maximum leaf spanning tree problem on acyclic digraphs. In: Solis-Oba, Roberto, Persiano, Giuseppe (eds.) Approximation and Online Algorithms, pp. 77\u201388. Springer, Berlin Heidelberg (2012)"},{"key":"2233_CR22","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/s00453-015-0080-0","volume":"77","author":"Roberto Solis-Oba","year":"2015","unstructured":"Solis-Oba, Roberto, Bonsma, Paul S., Lowski, Stefanie: A 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Algorithmica 77, 374\u2013388 (2015). https:\/\/doi.org\/10.1007\/s00453-015-0080-0","journal-title":"Algorithmica"},{"key":"2233_CR23","doi-asserted-by":"crossref","unstructured":"Thiery, Theophile, Ward, Justin: An improved approximation for maximum weighted k-set packing. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1138\u20131162. Society for Industrial and Applied Mathematics, (2023)","DOI":"10.1137\/1.9781611977554.ch42"},{"key":"2233_CR24","doi-asserted-by":"crossref","unstructured":"Trevisan, Luca: Non-approximability results for optimization problems on bounded degree instances. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC \u201901, pp. 453-461, New York, NY, USA, (2001)","DOI":"10.1145\/380752.380839"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02233-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02233-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02233-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:12:03Z","timestamp":1777360323000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02233-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,24]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["2233"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02233-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,24]]},"assertion":[{"value":"15 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}