{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:28:28Z","timestamp":1750307308624,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,9,1]],"date-time":"2011-09-01T00:00:00Z","timestamp":1314835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GRK 1408"],"award-info":[{"award-number":["GRK 1408"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>\n            An out-tree\n            <jats:italic>T<\/jats:italic>\n            of a directed graph\n            <jats:italic>D<\/jats:italic>\n            is a rooted tree subgraph with all arcs directed outwards from the root. An out-branching is a spanning out-tree. By \u2113(\n            <jats:italic>D<\/jats:italic>\n            ) and \u2113\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>D<\/jats:italic>\n            ), we denote the maximum number of leaves over all out-trees and out-branchings of\n            <jats:italic>D<\/jats:italic>\n            , respectively.\n          <\/jats:p>\n          <jats:p>\n            We give fixed parameter tractable algorithms for deciding whether \u2113\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) \u2265\n            <jats:italic>k<\/jats:italic>\n            and whether \u2113(\n            <jats:italic>D<\/jats:italic>\n            ) \u2265\n            <jats:italic>k<\/jats:italic>\n            for a digraph\n            <jats:italic>D<\/jats:italic>\n            on\n            <jats:italic>n<\/jats:italic>\n            vertices, both with time complexity 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              log\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u00b7\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            . This answers an open question whether the problem for out-branchings is in FPT, and improves on the previous complexity of 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              log\n              <jats:sup>2<\/jats:sup>\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u00b7\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            in the case of out-trees.\n          <\/jats:p>\n          <jats:p>\n            To obtain the complexity bound in the case of out-branchings, we prove that when all arcs of\n            <jats:italic>D<\/jats:italic>\n            are part of at least one out-branching, \u2113\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) \u2265 \u2113(\n            <jats:italic>D<\/jats:italic>\n            )\/3. The second bound we prove in this article states that for strongly connected digraphs\n            <jats:italic>D<\/jats:italic>\n            with minimum in-degree 3, \u2113\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) \u2265 \u0398(\u221a\n            <jats:italic>n<\/jats:italic>\n            ), where previously \u2113\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) \u2265 \u0398(3\u221a\n            <jats:italic>n<\/jats:italic>\n            ) was the best known bound. This bound is tight, and also holds for the larger class of digraphs with minimum in-degree 3 in which every arc is part of at least one out-branching.\n          <\/jats:p>","DOI":"10.1145\/2000807.2000812","type":"journal-article","created":{"date-parts":[[2011,9,27]],"date-time":"2011-09-27T14:02:19Z","timestamp":1317132139000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree"],"prefix":"10.1145","volume":"7","author":[{"given":"Paul","family":"Bonsma","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frederic","family":"Dorn","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,9,28]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 27th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'07)","volume":"4855","author":"Alon N.","unstructured":"Alon , N. , Fomin , F. V. , Gutin , G. , Krivelevich , M. , and Saurabh , S . 2007a. Better algorithms and bounds for directed maximum leaf problems . In Proceedings of the 27th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'07) . Lecture Notes in Computer Science , vol. 4855 . Springer-Verlag, Berlin, 316--327. Alon, N., Fomin, F. V., Gutin, G., Krivelevich, M., and Saurabh, S. 2007a. Better algorithms and bounds for directed maximum leaf problems. In Proceedings of the 27th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'07). Lecture Notes in Computer Science, vol. 4855. Springer-Verlag, Berlin, 316--327."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 34th International Colloquium on Automata, Languages, and Programming (ICALP'07)","volume":"4596","author":"Alon N.","unstructured":"Alon , N. , Fomin , F. V. , Gutin , G. , Krivelevich , M. , and Saurabh , S . 2007b. Parameterized algorithms for directed maximum leaf problems . In Proceedings of the 34th International Colloquium on Automata, Languages, and Programming (ICALP'07) . Lecture Notes in Computer Science , vol. 4596 . Springer-Verlag, Berlin, 352--362. Alon, N., Fomin, F. V., Gutin, G., Krivelevich, M., and Saurabh, S. 2007b. Parameterized algorithms for directed maximum leaf problems. In Proceedings of the 34th International Colloquium on Automata, Languages, and Programming (ICALP'07). Lecture Notes in Computer Science, vol. 4596. Springer-Verlag, Berlin, 352--362."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_4_1","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"Bang-Jensen J.","year":"2000","unstructured":"Bang-Jensen , J. and Gutin , G . 2000 . Digraphs: Theory, Algorithms and Applications . Springer-Verlag , Berlin . Bang-Jensen, J. and Gutin, G. 2000. Digraphs: Theory, Algorithms and Applications. Springer-Verlag, Berlin."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/645726.667215"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'03)","volume":"2747","author":"Bonsma P.","unstructured":"Bonsma , P. , Br\u00fcggemann , T. , and Woeginger , G. J . 2003. A faster FPT algorithm for finding spanning trees with many leaves . In Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'03) . Lecture Notes in Computer Science , vol. 2747 . Springer-Verlag, Berlin, 259--268. Bonsma, P., Br\u00fcggemann, T., and Woeginger, G. J. 2003. A faster FPT algorithm for finding spanning trees with many leaves. In Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'03). Lecture Notes in Computer Science, vol. 2747. Springer-Verlag, Berlin, 259--268."},{"key":"e_1_2_1_9_1","unstructured":"Bonsma P. and Dorn F. 2007. An FPT algorithm for directed spanning k-leaf. http:\/\/arxiv.org\/abs\/0711.4052.  Bonsma P. and Dorn F. 2007. An FPT algorithm for directed spanning k-leaf. http:\/\/arxiv.org\/abs\/0711.4052."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN'08)","volume":"4957","author":"Bonsma P.","unstructured":"Bonsma , P. and Zickfeld , F . 2008. Spanning trees with many leaves in graphs without diamonds and blossoms . In Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN'08) . Lecture Notes in Computer Science , vol. 4957 . Springer-Verlag, Berlin, 531--543. Bonsma, P. and Zickfeld, F. 2008. Spanning trees with many leaves in graphs without diamonds and blossoms. In Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN'08). Lecture Notes in Computer Science, vol. 4957. Springer-Verlag, Berlin, 531--543."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-005-3517-6"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374404"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.48"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_7"},{"key":"e_1_2_1_15_1","volume-title":"Dagstuhl Seminar Proceedings","volume":"07281","author":"Demaine E.","year":"2007","unstructured":"Demaine , E. , Gutin , G. , Marx , D. , and Stege , U . 2007. 07281 open problems \u2013 structure theory and FPT algorithmics for graphs, digraphs and hypergraphs . In Dagstuhl Seminar Proceedings , vol. 07281 , Schloss Dagstuhl, Dagstuhl, Germany. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/ 2007 \/1254. Demaine, E., Gutin, G., Marx, D., and Stege, U. 2007. 07281 open problems \u2013 structure theory and FPT algorithmics for graphs, digraphs and hypergraphs. In Dagstuhl Seminar Proceedings, vol. 07281, Schloss Dagstuhl, Dagstuhl, Germany. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2007\/1254."},{"volume-title":"Graph Theory","author":"Diestel R.","key":"e_1_2_1_16_1","unstructured":"Diestel , R. 1997. Graph Theory . Springer-Verlag , Berlin . Diestel, R. 1997. Graph Theory. Springer-Verlag, Berlin."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v37:4"},{"key":"e_1_2_1_18_1","volume-title":"Progress in Computer Science and Applied Logic Senses","volume":"13","author":"Downey R. G.","unstructured":"Downey , R. G. , and Fellows , M. R . 1995. Parameterized computational feasibility. In Feasible Mathematics, II , Progress in Computer Science and Applied Logic Senses , vol. 13 , Birkh\u00e4user, Boston, MA, 219--244. Downey, R. G., and Fellows, M. R. 1995. Parameterized computational feasibility. In Feasible Mathematics, II, Progress in Computer Science and Applied Logic Senses, vol. 13, Birkh\u00e4user, Boston, MA, 219--244."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer-Verlag Berlin.  Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer-Verlag Berlin.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798599"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 20th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'00)","volume":"1974","author":"Fellows M. R.","unstructured":"Fellows , M. R. , McCartin , C. , Rosamond , F. A. , and Stege , U . 2000. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems . In Proceedings of the 20th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'00) . Lecture Notes in Computer Science , vol. 1974 . Springer-Verlag, Berlin, 240--251. Fellows, M. R., McCartin, C., Rosamond, F. A., and Stege, U. 2000. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In Proceedings of the 20th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'00). Lecture Notes in Computer Science, vol. 1974. Springer-Verlag, Berlin, 240--251."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 26th Symposium on Theoretical Aspects of Computer Science (STACS'09)","author":"Fernau H.","year":"2009","unstructured":"Fernau , H. , Fomin , F. V. , Lokshtanov , D. , Raible , D. , Saurabh , S. , and Villanger , Y . 2009. Kernel(s) for problems with no kernel: On out-trees with many leaves . In Proceedings of the 26th Symposium on Theoretical Aspects of Computer Science (STACS'09) , Schloss Dagstuhl, Dagstuhl, Germany, 421--432. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/ 2009 \/1843. Fernau, H., Fomin, F. V., Lokshtanov, D., Raible, D., Saurabh, S., and Villanger, Y. 2009. Kernel(s) for problems with no kernel: On out-trees with many leaves. In Proceedings of the 26th Symposium on Theoretical Aspects of Computer Science (STACS'09), Schloss Dagstuhl, Dagstuhl, Germany, 421--432. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2009\/1843."},{"key":"e_1_2_1_23_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag Berlin.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag Berlin."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2009.02.011"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68880-8_23"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm039"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404010"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92182-0_26"},{"volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications","author":"Niedermeier R.","key":"e_1_2_1_30_1","unstructured":"Niedermeier , R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications , vol. 31 , Oxford University Press , Oxford, UK . Niedermeier, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, vol. 31, Oxford University Press, Oxford, UK."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.148"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1288107.1288111"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/647908.739992"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000807.2000812","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2000807.2000812","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:00:03Z","timestamp":1750244403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000807.2000812"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1145\/2000807.2000812"],"URL":"https:\/\/doi.org\/10.1145\/2000807.2000812","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2011,9]]},"assertion":[{"value":"2008-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}